Recursion and the call stack

Introduction

A function that calls itself is recursive. Every call gets its own frame on the call stack, with its own copy of the parameters.

Some problems are defined in terms of smaller copies of themselves, and recursion lets the code say exactly that. It is also the clearest way of seeing how the call stack works.

How it works

Two calls per call

fib(n) calls itself twice, so the number of calls grows very fast:

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("fib(5) = %d\n", fib(5));
    return 0;
}

Count the frames in the visualizer: even fib(5) makes 15 calls. This is why real programs store results they have already worked out.

No base case

Without a base case, the calls never stop. Each frame uses stack memory, and real C crashes with a "segmentation fault". StepVioz stops after 100 nested calls in the visualizer and explains:

#include <stdio.h>

int sum_down(int n) {
    return n + sum_down(n - 1);
}

int main(void) {
    printf("%d\n", sum_down(3));
    return 0;
}

Syntax

int f(int n) {
    if (n <= 1) {        // base case
        return 1;
    }
    return n * f(n - 1); // recursive case
}

Example

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(void) {
    int result = factorial(4);
    printf("4! = %d\n", result);
    return 0;
}

Step through and watch the frames pile up: factorial(4) calls factorial(3), which calls factorial(2), down to factorial(1). That one hits the base case and returns 1 without calling again. Then the frames finish one by one, from the top, each multiplying by its own n.

Line by line

1. main calls factorial(4).
2. Since 4 is not at most 1, the function needs factorial(3), and that frame waits.
3. The calls go on until factorial(1) reaches the base case and returns 1.
4. Each waiting frame multiplies its own n by the result it got: 2, then 6, then 24.
5. main stores 24 and prints it.

Expected result

4! = 24

In the real world

File system tools walk folders recursively, and compilers process nested expressions that way. Programs for small devices often avoid recursion, because their stacks are tiny.

Common mistakes

• No base case, or a base case that is never reached (for example, n == 0 when n starts negative).
• Not moving towards the base case: return n * factorial(n);.
• Forgetting return on the recursive call: factorial(n - 1); throws the result away.

Best practices

• Write the base case first.
• Check that each call moves closer to it.
• Use a loop when the recursion could go very deep.

Summary

A recursive function calls itself on a smaller problem and stops at a base case. Each call has a frame of its own, and without a base case the stack runs out.

Mark lesson complete