Recursion
Lesson 1 of 2
1Recursion (C - Recursion)
An approach entirely different from loops: a function that calls itself to solve a smaller version of the same problem, until it reaches a case simple enough to solve directly.
What the picture shows: Each call pushes a frame on the stack until the base case, then the values return one by one and the frames are popped.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
Recursion is like Russian matryoshka dolls: open a doll and find a smaller one, open it and find a smaller one, until the tiniest doll that does not open. A function that calls itself solves a problem by solving a smaller copy of it, until it reaches an easy case whose answer is known.
Every recursive function needs a base case where it stops and a recursive step that moves the input towards it. Each call takes a frame on the call stack, which is why deep recursion can overflow it. Examples include factorial, Fibonacci and tree search.
Before You Start
📞Function calls
You need a basic understanding of how one function calls another in C, and the idea that each call gets its own local variables, because the core of recursion is a function calling itself, making the caller and the callee the same entity with different copies of their variables.
🔀Conditional statements
Every recursive function relies on if to decide: have we reached the base case (stop), or do we call the function again? Without a solid grasp of how if/else works and when a condition is satisfied, you'll struggle to trace nested call chains.
🧮Pointers, basics
Several recursive patterns in C (like traversing an array or a string recursively) depend on moving a pointer forward one step per call, so if you're not comfortable with the idea that arr + 1 advances the pointer by one element, review pointer arithmetic basics first.
The Core Idea: A Base Case + A Recursive Call
To really understand recursion, you have to see it as a way of defining a problem's solution, not as a step-by-step recipe for computing it: a recursive function doesn't "explain" how to solve the problem, it defines its solution in terms of the solution to a smaller version of the same problem, exactly the way a natural number is defined by mathematical induction: one base case (usually zero) plus a rule that builds every other number from the one before it. And just as a proof by induction needs two pillars it cannot do without, every correct recursive function needs two indispensable pillars:
1Base Case
The simplest case, solved directly with no further call, the counterpart of the "n = 0" case in a proof by induction. Its real job is twofold: first, it's the actual stopping point that keeps calls from continuing forever; second, it's the only source of a "ready" value that everything else can build on, every other call has no ready value of its own, it's waiting on the result of a smaller call. If the base case is missing entirely, or written with a condition that's never satisfied for some input (say, calling factorial(-3) on a function that only checks n <= 1, while the input is negative and moves away from zero instead of toward it), the calls never stop: each one waits on the result of a call that hasn't happened yet, and frames keep piling up in memory until they exhaust the space reserved for the call stack, typically 8 MB per thread by default on Linux, crashing the program with a stack overflow.
2Recursive Step
The call the function makes to itself, where the input isn't just "smaller" in some vague, intuitive sense, it has to be smaller by a measure that is guaranteed to reach the base case after a finite number of steps. In factorial, that measure is n itself: every call passes n - 1, so the value drops by exactly one each time, and since there's no infinite chain of integers strictly between any positive number and zero, hitting n <= 1 is mathematically guaranteed. The exact mistake many people fall into is writing a call that "looks" recursive but doesn't actually move the input any closer to the base case, calling the function with the same value n instead of n - 1 (an easy typo), or with a value that moves away from the base case instead of toward it. In every one of these cases the code is recursive in form only, but in practice it's an infinite loop, no different in substance from having no base case at all.
Figure 1, each call waits for the result of the call after it before it can finish its own computation; this is why there are two "phases": going down (each call calls the next) then coming back up (each call returns its value to whoever called it).
The two diagrams above show why you need both pillars together, not either one alone: a base case with no recursive step only solves the one trivial case; a recursive step with no base case never stops. The real guarantee of correctness works exactly like a proof by mathematical induction: if the base case holds, and if every recursive step builds the correct result assuming the smaller call it depends on is already correct (this assumption is exactly what's called the "inductive hypothesis"), then the result is correct for every possible input, which is precisely what happens in factorial(n): assuming factorial(n - 1) returns the correct value, n * factorial(n - 1) is necessarily the correct value for factorial(n).
Different Recursion Patterns
3Tail Recursion
The recursive call is the last operation in the function, nothing remains to be done after it returns. The crucial difference: since no computation is pending after the call, some compilers can transform it into a plain loop automatically (tail call optimization), avoiding frame accumulation entirely. In C, GCC with -O2 often does this.
4Tree Recursion
The function calls itself more than once per invocation, like computing Fibonacci: fib(n-1) + fib(n-2). The result is a call tree that branches out extremely fast, with the number of calls growing exponentially with the input size, this pattern needs techniques like memoization to avoid recomputing the same values thousands of times.
Comparison: Recursion vs. Iterative Loops
| Criterion | Recursion | Iteration (Loops) |
|---|---|---|
| Memory | Each call consumes a stack frame, risk of stack overflow with deep recursion | Only one or a few variables, no extra frame accumulation |
| Performance | Usually slower due to call/return overhead, but tail-call optimization eliminates the gap | Typically faster since it avoids the overhead of repeated function calls |
| Clarity | Much clearer for problems that naturally split into smaller copies of themselves (trees, graphs, divide & conquer) | Clearer for linear problems that advance step by step (counting, accumulation) |
How It Works, Step by Step: The Call Stack
Every function call, recursive or not, gets its own "frame" (stack frame) in memory, created automatically on entry to the function and torn down automatically on exit. This frame isn't an abstract box: it actually holds the return address, the exact point in the code the processor must jump back to once this particular call finishes, plus this call's own copy of its parameters and local variables, and usually a saved pointer to the previous frame (a saved base/frame pointer) used to find that previous frame quickly on return. The entire call stack is a fixed-size region of memory reserved in advance for each thread, typically 8 MB by default on Linux, and every new call "pushes" its frame on top of the previous one, automatically moving the stack pointer to reserve the space it needs. In recursion, these frames stack on top of each other with no exception for the fact that it's the same function, because every call to factorial(n), even though it's the same function name, is a completely independent entity with its own return address and its own copy of n that no other call shares:
📥1. The call
Each call to factorial(n) adds a new frame on top of the stack, holding its own copy of n and the return address pointing back to exactly wherever that call was made from. Even though every call executes exactly the same lines of code, each one is completely isolated from the others; changing n inside one call never changes the copy of n in another call, and that isolation is exactly what lets each call "see" a different value of the same-named variable.
🧱2. Stacking up
Frames pile up one after another until the base case is reached, and the stack's depth at any moment equals the number of currently active nested calls at that moment. Since every frame consumes real memory from the space reserved for the stack (proportional to the number and size of that function's local variables), the maximum possible recursion depth is practically bounded by that reserved space divided by the size of a single frame, which is exactly the direct link between a base case that's slow to reach (or missing) and the stack overflow error mentioned in Part One.
📤3. Unwinding
Once the base case is reached, the whole process runs in exact reverse: the topmost frame on the stack computes its value and returns it, through the return address saved inside it, to exactly the frame that called it, then that frame is removed from the stack, immediately shrinking the reserved space. This strictly reversed order, the last frame added is the first one removed, is known as LIFO discipline (Last In, First Out), and it's exactly what guarantees that every call receives precisely the result of the call it itself made, and no other, even with several nested calls to the same function name active at once.
Figure 2, every level in this diagram is a fully independent frame in memory: it holds its own copy of n and the exact return address it will hand its value back to; all four frames exist in memory at once only once the base case is reached, that simultaneous depth is exactly what can exhaust the limited space reserved for the stack if it repeats thousands of times.
int factorial(int n)
{
if (n <= 1) /* base case */
return (1);
return (n * factorial(n - 1)); /* recursive step */
}
Figure 3, Notice that n * factorial(n - 1) can't be computed until the inner call returns its value, that's exactly what forces the stack to wait before unwinding.
Worked Example: Summing an Array Recursively
The same pattern (base case + recursive step) applies to any problem that can be broken into a smaller version of itself:
int sum_array(int *arr, int size)
{
if (size == 0) /* base case: empty array */
return (0);
return (arr[0] + sum_array(arr + 1, size - 1));
}
Each call takes the "rest" of the array (moving the pointer forward one step and decreasing the size), until it reaches size zero and stops. The array itself is never copied: arr + 1 is pointer arithmetic that moves the pointer forward by exactly one element of type int (usually 4 bytes), producing a new reference that starts at the second element of the same array in memory, not a separate array. At the same time, size - 1 tells the new call that its "world" is now one element smaller. Moving the pointer forward and shrinking the size together guarantee that each call sees a genuinely smaller slice of the same array, so the chain reaches size zero (the base case) after a bounded number of steps exactly equal to the array's length.
Figure 4, each call receives a pointer moved one step further (arr+1, arr+2...) and a size one smaller each time; since the size keeps shrinking by a fixed step, reaching size zero (the base case) is guaranteed after a bounded number of calls, exactly like factorial in the previous diagram.
Myth vs. Reality
| Myth | Reality |
|---|---|
| Recursion is only used in academia and has no practical benefit | Recursion is the natural way to represent nested data structures (trees, JSON, file systems, DOM), most efficient sorting algorithms (merge sort, quicksort) and search algorithms (binary search trees) are fundamentally built on it. |
| Any recursive solution can be easily converted to a loop | Linear recursion (like factorial) can be converted directly. But tree recursion (like traversing a multi-branch tree) requires simulating an explicit stack to convert, and the resulting code is often more complex and harder to read than the recursive version. |
| Every recursive function uses more memory | True only for non-tail recursion. Tail recursion, when optimized by the compiler, reuses the same frame, no extra frames ever accumulate, working exactly like a loop in terms of memory usage. |
Practical Applications
🌲Tree Traversal
Tree data structures (binary search trees, the DOM in web pages, the file system) are recursive by nature: every node may contain child nodes of the same type. Traversing them is naturally expressed as a recursive function that visits the node then calls itself on each branch.
🔀Divide-and-Conquer Algorithms
Merge Sort and Quick Sort split the array in half, sort each half recursively, then merge them, exactly the same "base case + recursive step" pattern, but with two calls instead of one (tree recursion).
📂Directory Browsing
Any tool that browses a directory and all its subdirectories (like find or ls -R) works recursively: enter the directory, process its files, then call yourself on each subdirectory, the empty directory is the base case.
🧩Expression Parsing
Compilers and calculators parse expressions like (3 + (2 * 5)) recursively: every expression is either a simple number (base case) or an operation on two sub-expressions, a naturally recursive structure.
Deep Dive: Designing Recursion and Its Cost
We understood the call stack mechanism; here we turn that understanding into a design method: how to decide whether a problem suits recursion, how to design it, and how to know when it costs more than it is worth.
A design recipe: four questions
Figure 5, The recursion design recipe: trusting the smaller call is the secret of simplicity.
Question three is the "leap of faith": do not try to trace every call in your head at once; assume the call on the smaller problem works and focus only on how you add your own step. Question four is your insurance against infinite descent: if the input does not move closer to the base case on every call, the process never ends until the stack fills.
Common patterns
| Pattern | How the problem shrinks | Idea example |
|---|---|---|
| String or array | Handle one element then recurse on the rest | Printing a string character by character |
| Numbers | Decrease the number or drop a digit | Sum of a number’s digits |
| Divide and conquer | Split the problem in halves | Binary search |
| Accumulating in parameters | Pass the partial result as an extra parameter | When statics and loops are banned |
The "no loops, no static variables" constraints enforce a lovely idea: all state must travel through parameters and return values. If you need a counter, make it an extra parameter, usually wrapped by another function that starts it at zero.
Cost: when does recursion go bad?
Every call has a stack frame holding parameters, locals and the return address. Depth N means memory proportional to N, and the stack is limited (often a few megabytes on Linux), so very deep recursion crashes with a stack overflow. There is a subtler cost: naive recursion may recompute the same sub-problem repeatedly. A classic example is Fibonacci written with two branching calls: computing fib(5) evaluates fib(3) twice and fib(2) three times, and the work roughly doubles with each increase in input (exponential growth). The cure is storing earlier results (memoization) or converting to a loop.
Figure 6, The naive Fibonacci call tree: the repeated nodes (fib(3) and fib(2)) are wasted work.
| Recursion fits | A loop fits |
|---|---|
| Branching structures: trees, directories, nested expressions | Simple counting or summing over a known range |
| Divide and conquer and backtracking | Very great depth with a limited stack |
| The solution is much clearer in recursive form | Performance-critical code that cannot afford call overhead |
Draw a trace table: one row per call with its arguments and its decision (base case or step). When the table ends as you expect, your design is right.
Try it yourself
What happens to a recursive function whose base case never triggers for a given input?
Each call waits for a result from a call that has not happened yet. The frames use up the limited stack (often 8 MB) and the program crashes.
Two calls of factorial(n) are on the stack. What about n in each?
Each frame holds the return address and its own copy of parameters and locals, so calls are isolated although the code is the same.
When does a recursive function not pile up extra frames?
Optimised tail recursion behaves like a loop in memory. Non-tail recursion stacks one frame per level.
Quick Review Flashcards
Check Your Understanding
Why can't factorial(4) be computed immediately, why must it wait for factorial(3) to return?
Because computing factorial(4) mathematically depends on the result of factorial(3) (it's 4 × factorial(3)); you can't multiply a number by a result that hasn't been computed yet, so the call is forced to wait until the whole chain completes down to the base case.
If you wrote return factorial(n) instead of return factorial(n - 1), what would happen?
The input would never change between calls, every call passes the same value n, so it never gets any closer to the base case. The result is exactly the same as forgetting the base case entirely: infinite calls and a stack overflow crash.
How many frames are on the stack at once when computing factorial(100)?
Exactly 100 frames, one for each value from 100 down to 1 (the base case). No frame gets removed until the chain reaches the base case and unwinding begins, so the maximum depth equals the original input value.
Why is a base case not enough?
Because every call must move toward it; otherwise it may never be reached and the stack fills.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Articles2
Tools1
Done with this lesson?
Sign in to save your progress.