Every well-formed recursive function must include which two components?
Choose an answer, then check it.
Computer Science Fundamentals · Foundations
Recursion
On this page 9 sections
In 30 seconds
Recursion A technique in which a function accomplishes a task by calling itself on a smaller part of that task. Full entry → is a technique where a function solves a problem by calling itself on a smaller version of that problem. Every correct recursive function has two parts: a Base case The condition simple enough to solve directly, with no further recursive call; it stops the recursion. Full entry → that stops the calls, and a Recursive case The part of a recursive function that reduces the problem to smaller subproblems, calls itself on them, and combines the results. Full entry → that moves toward the base case. Each call is stacked on the one before it, so the work unwinds once the base case is reached. Miss the base case and the calls never stop.
Why this matters
Recursion is one of the two fundamental ways to repeat work, alongside Iteration Repeating work with a loop and explicit variables, the alternative to recursion. Full entry →, and it is the natural fit for anything with a nested or self-similar structure: file trees, parsers, sorting algorithms like merge sort and quicksort, and traversals of trees and graphs. Courses in data structures, algorithms, and programming languages assume you can read and write a recursive function fluently. Learning it well also builds a habit that pays off elsewhere: define a problem in terms of a smaller version of itself, pin down the case that needs no further work, and trust the rest to follow. The same discipline underlies mathematical induction and divide-and-conquer design.
The college version
What recursion is
Recursion is an algorithmic technique in which a function, to accomplish a task, calls itself on some part of that task. The definition sounds circular, and in a sense it is: a recursive function is defined partly in terms of itself. What keeps it from being useless circularity is that each call works on a smaller or simpler input than the one before, so the problem shrinks with every step and eventually becomes trivial. A recursive function is still an ordinary function. It has a name, takes arguments, and can return a value. The only thing that makes it recursive is that somewhere in its body it invokes itself. This lets you describe a large task by saying how to reduce it to a smaller instance of the same task, rather than spelling out every step. Problems with a naturally nested or self-similar shape, such as walking a folder that contains folders, are often far clearer written this way than with loops.
The two required parts: base case and recursive case
Every correct recursive function needs two ingredients. The base case is the situation simple enough to answer directly, with no further recursion. It is the stopping point. The recursive case handles everything else: it breaks the problem into one or more smaller subproblems, calls the function on them, and combines the results into the answer. The recursive case must always move the input toward the base case, or the shrinking never happens. Think of factorial: the base case is factorial(0) = 1, answered outright; the recursive case is factorial(n) = n * factorial(n - 1), which reduces n by one on each call and so marches steadily down to zero. If you write the recursive case but forget the base case, or write a base case the input can never actually reach, the function has no place to stop. That failure is not a minor bug; it is the defining way recursion goes wrong.
The call stack and stack overflow
To understand why an unreachable base case is so damaging, you have to know how a computer keeps track of function calls. Every time a function is called, the program sets aside a small block of memory called a Stack frame The block of memory holding a single call's arguments, local variables, and return location. Full entry →, holding that call's arguments, local variables, and the place to return to when it finishes. These frames live on the Call stack The region of memory that records active function calls, one frame per call, in last-in, first-out order. Full entry →, which behaves exactly like the stack data structure: the most recently added frame is the first one removed, last in, first out. (Stacks are their own topic; here the point is only that the call stack is one.) During recursion, each call pushes a new frame before the previous call has returned, so the frames pile up. When the base case is finally reached, that call returns, its frame is popped, and control flows back up through the waiting frames, each finishing its own bit of work. If the base case is never reached, frames keep piling up without ever being popped. The stack has a finite size, so eventually it runs out of room. This is a Stack overflow The error that occurs when the call stack runs out of space, typically from unbounded recursion. Full entry →. Python guards against it with a Recursion limit A cap on how deep recursion may go before the language stops it; in Python the default is 1000, after which a RecursionError is raised. Full entry →, 1000 by default, and raises a RecursionError rather than letting the interpreter crash; other languages report a stack overflow in their own way.
Recursion versus iteration
Recursion is not the only way to repeat work. Iteration, using a loop such as for or while, is the alternative, and any computation you can express one way you can express the other. The difference is where the bookkeeping lives. A loop repeats using explicit variables you manage yourself, and it reuses one region of memory as it goes. Recursion repeats by calling itself and lets the call stack hold the partial state of every unfinished call, which costs stack space proportional to how deep the recursion goes. That is the trade-off: recursion often expresses self-similar problems more directly and closely mirrors their mathematical definition, while iteration avoids the per-call stack cost and cannot hit a recursion limit. Neither is always right. Choose recursion when the problem's structure is itself recursive and the depth stays modest; reach for a loop when the repetition is flat and the depth could grow large.
Eli explains
The same idea, in plain words
Explain it like I’m 10
Recursion is solving a big job by doing one small piece and then handing the rest of the job, now slightly smaller, to another copy of yourself. Each copy does the same thing: one small piece, then pass the rest along. This only works if there is a moment when the job is so tiny that a copy can just finish it without passing anything on. That stopping moment is the base case. Without it, the copies keep handing work down forever and the whole thing jams up.
Picture it like this
Imagine a line of people passing a sealed box back to find out how many boxes are inside. Each person opens their box, finds a smaller box, and passes it to the next person, saying 'you count yours and tell me.' The last person opens a box that is empty, says 'zero,' and hands the answer back. Now each person adds one and passes their total forward, until the first person has the full count. The empty box is the base case; the passing-back is the unwinding.
Where the picture stops working
The box line makes the calls look like different people, but in a real program every call runs the same single function; what actually differs is each call's own frame of variables on the call stack. And a real base case is a condition the function tests for, not a physical empty box, so the danger is subtler: if the boxes never got empty, the line would never stop, which is exactly the stack overflow the analogy cannot show you running out of people.
Worked example
Take factorial(n), defined as 1 when n is 0 (the base case) and n * factorial(n - 1) otherwise (the recursive case). Trace factorial(4). The winding-up: factorial(4) needs factorial(3), which needs factorial(2), which needs factorial(1), which needs factorial(0). Now four frames are stacked and waiting. factorial(0) hits the base case and returns 1 with no further call. The unwinding then runs back up: factorial(1) returns 1 * 1 = 1; factorial(2) returns 2 * 1 = 2; factorial(3) returns 3 * 2 = 6; factorial(4) returns 4 * 6 = 24. So factorial(4) = 24, and the function was called five times in all (n = 4, 3, 2, 1, 0). Verified by running the code: factorial(4) evaluates to 24, matching 4 * 3 * 2 * 1.
Key takeaway
A recursive function solves a problem in terms of a smaller version of itself; it must have a base case that stops the recursion and a recursive case that moves toward it, because every call stacks a frame and an unreachable base case overflows the stack.
Quick check
3 questions here, of 5 in this lesson’s practice set. Answers stay hidden until you check.
A recursive function is written so that its base case can never actually be reached. What is the most likely result when it runs?
Choose an answer, then check it.
Using factorial(n) = 1 when n is 0 and n * factorial(n - 1) otherwise, what does factorial(3) evaluate to, and how many times is factorial called in total, counting the base case?
Choose an answer, then check it.
Study tools & related lessonsYou’ll learn to · Common mistakes · Easily confused · Key vocabulary · Related
You’ll learn to
- Define recursion as a function that calls itself on a smaller subproblem.
- Distinguish the base case from the recursive case and explain the role of each.
- Explain how the call stack records recursive calls and why a missing base case causes a stack overflow.
- Trace a simple recursive function, such as factorial, through its wind-up and unwinding.
- Compare recursion with iteration as alternative ways to repeat work.
Common mistakes
Writing the recursive case but forgetting the base case.
Always include a base case the input can actually reach; without it the calls never stop and the stack overflows (a RecursionError in Python).
Writing a base case that the recursive case never approaches, for example decreasing n but testing for n == -1 when n starts positive and can skip past it, or not shrinking the input at all.
Make sure every recursive call moves the input strictly toward the base case, so the base case is guaranteed to be hit.
Believing recursion is a fundamentally different kind of power than loops.
Recursion and iteration can compute the same things; recursion trades call-stack space for a structure that often mirrors the problem more directly.
Thinking a deep but correct recursion is always safe.
Even correct recursion is bounded by the call stack; very deep recursion can exceed the limit (Python's default is 1000), so for large, flat repetition a loop may be the better choice.
Confusing the call stack with the stack data structure as separate ideas.
The call stack is a stack: frames are pushed and popped last-in, first-out. Understanding one explains the other.
Easily confused
Base case vs. Recursive case
The base case is solved directly and makes no further call, stopping the recursion; the recursive case shrinks the problem and calls the function again.
Recursion vs. Iteration
Recursion repeats by a function calling itself and stores partial state on the call stack; iteration repeats with a loop and explicit variables in reused memory.
Infinite recursion vs. An infinite loop
Both never terminate, but infinite recursion keeps allocating stack frames and eventually overflows the stack, while an infinite loop reuses the same memory and can run indefinitely without exhausting the stack.
Key vocabulary
- Recursion
- A technique in which a function accomplishes a task by calling itself on a smaller part of that task.
- Base case
- The condition simple enough to solve directly, with no further recursive call; it stops the recursion.
- Recursive case
- The part of a recursive function that reduces the problem to smaller subproblems, calls itself on them, and combines the results.
- Call stack
- The region of memory that records active function calls, one frame per call, in last-in, first-out order.
- Stack frame
- The block of memory holding a single call's arguments, local variables, and return location.
- Infinite recursion
- Recursion whose base case is missing or never reached, so the calls continue without end.
- Stack overflow
- The error that occurs when the call stack runs out of space, typically from unbounded recursion.
- Iteration
- Repeating work with a loop and explicit variables, the alternative to recursion.
- Recursion limit
- A cap on how deep recursion may go before the language stops it; in Python the default is 1000, after which a RecursionError is raised.
Sources & references
- recursion - Dictionary of Algorithms and Data Structures (DADS) — National Institute of Standards and Technology (NIST)
- stack - Dictionary of Algorithms and Data Structures (DADS) — National Institute of Standards and Technology (NIST)
- Think Python (3rd ed.), Chapter 5: Conditionals and Recursion — Allen B. Downey / Green Tea Press
- sys - System-specific parameters and functions (recursion limit) — Python Software Foundation
- Think Python, 2e — Chapter 3: Functions — Allen B. Downey / Green Tea Press
EliExplains lessons are original prose written from the open, credible references above. See Copyright & Licensing.
Researched 2026-08-19
Educational content only. It is not medical, legal or professional advice. Found an error? Tell us.