Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 135 Β· Functions

Recursion

Learn recursion in C - base cases, the call stack, factorial, Fibonacci, fast power and Tower of Hanoi, stack overflow, and when a loop is the better choice.

A recursive function is a function that calls itself. That sounds like a recipe for an endless loop, and it is, unless every call works on a smaller version of the problem and there is a version so small that the function can answer it directly. Many problems have exactly that shape: the factorial of 5 is 5 times the factorial of 4; the files in a folder are the files in it plus the files in each subfolder; a sorted list is a sorted left half merged with a sorted right half.

In this lesson you'll learn the two parts every recursive function needs, watch the call stack grow and shrink, work through the classic examples (factorial, Fibonacci, power, Tower of Hanoi), and see the costs: repeated work, stack overflow, and when a plain loop is the better tool.

Base case and recursive case

Every correct recursive function has two parts:

  1. A base case: an input small enough to answer without recursion. It stops the chain of calls.
  2. A recursive case: the function calls itself with an input that is closer to the base case, then uses the result.

Factorial is the textbook example. The factorial of n, written n!, is the product 1 Γ— 2 Γ— … Γ— n, and 0! is defined as 1. That definition is naturally recursive: n! = n Γ— (n βˆ’ 1)!.

C Recursive factorial

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The output ends with 20! = 2432902008176640000, which is the largest factorial that fits in a 64-bit unsigned long long. 21! would overflow and wrap around silently (see Integer Types).

Check the two rules: n == 0 is answered directly, and each call passes n - 1, which moves toward 0. Break either rule and the recursion never stops. Calling this factorial with a negative int would be a problem for a signed version, which is one reason the parameter is unsigned here.

How the call stack makes it work

Recursion works because every call gets its own copy of the parameters and local variables. They live in a stack frame, a block of memory on the call stack that is created when the function is called and removed when it returns. A call to factorial(3) creates a frame where n is 3; inside it, factorial(2) creates a new frame where n is 2, and so on. Nothing gets overwritten, because each frame is separate.

You can watch the frames pile up and unwind by printing with indentation equal to the depth:

C Tracing the calls

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The trace shows two phases. On the way down, each call is suspended in the middle of n * factorial(n - 1), waiting for its inner call. At the bottom, the base case returns 1. On the way up, each waiting frame receives the result, does its multiplication and returns: 1, 1, 2, 6, 24. (%*s with an empty string prints depth * 2 spaces, a handy trick for indentation.)

That waiting is the key to understanding recursion. Code before the recursive call runs on the way down, in order; code after it runs on the way up, in reverse order. This program uses that to print digits in both directions:

C Before or after the recursive call

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The first line prints 17504 and the second 40571. The only difference is whether printf comes before or after the recursive call. digits_in_order is also a neat way to print a number without knowing how many digits it has, and it works for any base if you replace 10 (try 2 for binary).

Fibonacci and the cost of repeated work

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, … where each number is the sum of the two before it. The definition translates directly into C, with two recursive calls:

C
unsigned long long fib(unsigned n) {
    if (n < 2) {
        return n;                        /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

It's correct, but horribly slow. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again, and so on. The same values are recomputed over and over, and the number of calls roughly multiplies by 1.6 for every step in n. Let's count:

C Counting Fibonacci calls

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

fib(30) takes 2,692,537 calls recursively. fib(50) would take about 40 billion calls and run for a long time; the loop version computes fib(90) = 2880067194370816120 instantly. (The static counter is a variable that outlives every call; Scope and Storage Classes explains it.)

The lesson isn't "recursion is slow". Recursion that recomputes the same subproblems is slow. You can fix it by remembering results (memoization: store fib(k) in an array the first time you compute it), or by noticing that a loop does the job naturally, as here.

Fast power: halving the problem

Recursion shines when each call cuts the problem in half. Computing xⁿ by multiplying x by itself n times takes n steps. But xⁿ = (x^(n/2))Β² when n is even, and x Γ— x^(nβˆ’1) when it's odd. Each halving step removes half the work:

C Exponentiation by squaring

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

1.001 to the power 1000 takes only 16 calls instead of 1000, and 2⁢² takes 11. That last result is stored in big before printing because the order in which a call's arguments are evaluated is unspecified (Parameters and Return Values): with power(2.0, 62) and steps as two arguments of the same printf, GCC reads steps first and prints 0 calls. Notice double half = power(x, n / 2);: writing power(x, n / 2) * power(x, n / 2) would make two identical calls and throw the advantage away, the same trap as Fibonacci. The standard library's pow from The Math Library handles real exponents; this technique is what you use for integer powers, matrix powers and modular arithmetic in cryptography.

Tower of Hanoi: where recursion is the natural answer

In the Tower of Hanoi puzzle, you move a stack of n disks from peg A to peg C, one disk at a time, never placing a larger disk on a smaller one, using peg B as a helper. Solving it with loops is tricky. The recursive solution is three lines of thinking:

  1. Move the top n βˆ’ 1 disks from A to B (using C as the helper).
  2. Move the largest disk from A to C.
  3. Move the n βˆ’ 1 disks from B to C (using A as the helper).
C Tower of Hanoi

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Three disks take 7 moves; in general n disks take 2ⁿ βˆ’ 1. The recursive version mirrors the idea exactly, which is the real strength of recursion: for problems that are self-similar (trees, nested structures, divide-and-conquer algorithms), the recursive code reads like the definition. You'll use it for binary search trees and for merge sort and quicksort in Sorting and Searching Algorithms.

Stack overflow

Every active call occupies a stack frame, and the stack is limited, typically 8 MB for the main thread on Linux and 1 MB on Windows. If recursion goes too deep, the program runs out of stack space: a stack overflow. In C that's undefined behavior; in practice the operating system kills the program, usually with a segmentation fault and no helpful message.

The two usual causes:

  • A missing or unreachable base case. For example int count_down(int n) { return count_down(n - 1); }, or a base case of n == 0 when n starts negative.
  • Legitimately deep recursion. Summing a list of 10 million numbers recursively needs 10 million frames, far more than the stack holds, even though the logic is correct.
C
/* Don't do this: one stack frame per element. */
long sum_recursive(const int *values, size_t count) {
    if (count == 0) {
        return 0;
    }
    return values[0] + sum_recursive(values + 1, count - 1);
}

With a few thousand elements this works; with millions it crashes, and a simple loop has neither problem. Recursion depth that grows with the input size (linear depth) is a warning sign. Depth that grows with the logarithm of the input, like fast power or binary search, is always safe: halving a billion takes only about 30 steps.

When the recursive call is the very last thing a function does (a tail call), optimizing compilers can reuse the current stack frame instead of creating a new one. GCC and Clang do this at -O2, but the C standard doesn't require it, and n * factorial(n - 1) isn't a tail call anyway, because the multiplication happens after the call returns. Never rely on tail-call optimization to keep a deep recursion safe.

Recursion or a loop?

Anything you can write recursively you can also write with a loop (sometimes with an explicit stack), and vice versa. Pick by clarity and by depth:

Prefer recursion when Prefer a loop when
The data is recursive: trees, nested lists, directory structures You walk a sequence: arrays, lines, a range of numbers
The algorithm is divide-and-conquer (merge sort, quicksort, binary search) The depth would grow with the input size
The recursive version is much shorter and clearer The recursive version recomputes subproblems
Depth is small or logarithmic Every bit of speed matters (calls have some overhead)

Factorial and Fibonacci are great for learning recursion, but in production C you'd compute them with loops. Hanoi, tree traversal and quicksort are where recursion earns its keep.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. What does f(4) return? int f(int n) { if (n == 0) return 0; return n + f(n - 1); }

    f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + 1 + f(0) = 10. The base case f(0) returns 0.
  2. 2. What does show(3) print? void show(int n) { if (n == 0) return; show(n - 1); printf("%d ", n); }

    The printf comes after the recursive call, so it runs on the way back up. The deepest call that prints is show(1), so the output is 1 2 3.
  3. 3. Why is the naive two-call recursive Fibonacci function so slow?

    fib(n - 1) and fib(n - 2) both recompute smaller Fibonacci numbers many times. fib(30) needs millions of calls; a loop needs 29 steps.
  4. 4. What happens when you call int g(int n) { if (n == 0) return 0; return g(n - 2); } with g(5)?

    The base case n == 0 is never reached for odd inputs. Each call adds a stack frame until the stack runs out, usually crashing with a segmentation fault.
  5. 5. Which recursion is safe even for an input of one billion?

    Halving a billion reaches 1 in about 30 steps, so the stack depth stays tiny. One-element-per-call recursion would need a billion stack frames.

Summary

  • A recursive function calls itself. It needs a base case that is answered directly and a recursive case that moves toward it.
  • Each call has its own stack frame with its own parameters and locals. Code before the recursive call runs on the way down; code after it runs on the way back up.
  • Recursion that recomputes the same subproblems (naive Fibonacci) is exponentially slow; remember results or use a loop.
  • Halving the problem (fast power, binary search) gives tiny, logarithmic depth.
  • Too-deep recursion overflows the limited call stack and crashes the program; avoid recursion whose depth grows with the input size.
  • Use recursion for self-similar problems such as trees and divide-and-conquer; use loops for walking sequences.

Next: Scope and Storage Classes, where you'll learn where variables live, how long they last and who can see them.