← 🔁 Functions & Recursion
Subtopic 3 of 5

5.3Recursion and the call stack

The idea

Recursion is a function that calls itself on a smaller problem until a base case stops it. Each call has its own frame on the call stack.

Think of it like this: Russian dolls: you open each doll to find a smaller one, until the smallest; then you close them in the reverse order.

Why it exists

Output order depends on whether the work happens before the recursive call (in call order) or after it (reverse order).

How it works

  1. Check the base case first.
  2. Calls go down: each pushes a new frame with its own copies of the parameters.
  3. At the base case the calls start returning, last call first.
  4. Statements after the recursive call run on the way back up.

Worked example: bin(6) printing n % 2 after the call

Calls go bin(6) → bin(3) → bin(1) → bin(0). Then 1 % 2 = 1 prints, then 3 % 2 = 1, then 6 % 2 = 0. Output 110: the binary digits of 6.

Now play with it

  • →Run work after the call and read the call tree on the bottom.
  • →Compare it with work before the call, which prints in the opposite order.

bin prints n % 2 AFTER the recursive call, so the deepest call prints first: the binary digits come out from the most significant end.

step 1 of 14
1#include <stdio.h>
2void bin(int n) {
3 if (n > 0) {
4 bin(n / 2);
5 printf("%d", n % 2);
6 }
7}
8int main() {
9 bin(6);
10 printf("\n");
11 return 0;
12}

The gold line is the statement about to run.

Call stack (top first)
main()
no variables yet
Output
Call tree so far (indent = recursion depth)

Check yourself

void p(int n) { if (n > 0) { p(n - 1); printf("%d", n); } } What does p(3) print?

Remember: Before the call = call order, after the call = reverse order; always find the base case.
Exam notes (the dense version)

A recursive function needs a base case and a step toward it. Each call gets its own activation record (parameters, locals, return address) on the stack; the calls unwind in last-in-first-out order. Work done before the recursive call happens in call order, work after it happens on the way back, which reverses the order (printing digits after the call prints them reversed).

Previous year questions: Functions & Recursion (11)

PYQs are grouped by topic, so this is the full set for Functions & Recursion; try the ones that match this subtopic. Open all 11 on the topic page.