Recursion trees; counting calls; work done before vs after the recursive call

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What two parts must every recursive function have? from Lesson 2.1.1
• What does free(p) do to p itself? from Lesson 1.7
• How many times does count++ run in for (i = 1; i <= 16; i *= 2) for (j = 1; j <= i; j++) count++;? from Lesson 1.2.2

1 · The Hook

🎣

A family invitation goes out: each person invites their two children, who each invite their two children. From one person, the invitations spread into a branching diagram, like a family tree drawn upside down. When a recursive function calls itself twice, its calls branch the same way, and the number of calls can grow very fast.

2 · Predict First

🤔

What does this print?

void p(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);     /* before the call: on the way down */
    p(n - 1);
    printf("%d ", n);     /* after the call: on the way back up */
}

int main(void)
{
    p(3);
    printf("\n");
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

3 2 1 1 2 3

The first printf runs on the way down (3, 2, 1). The second runs after the inner call has finished, on the way back up, so the same numbers appear in reverse (1, 2, 3).

Before vs after the recursive call

Code before the recursive call runs in the order of the calls (going down). Code after it runs in reverse order (coming back up). That is why the same printf placed before or after the call prints a number forwards or backwards:

void show(int n)
{
    if (n == 0)
        return;
    show(n / 10);
    printf("%d", n % 10);
}

void showRev(int n)
{
    if (n == 0)
        return;
    printf("%d", n % 10);
    showRev(n / 10);
}

int main(void)
{
    show(2027);
    printf(" ");
    showRev(2027);
    printf("\n");
    return 0;
}

Output

2027 7202

Recursion trees

A recursion tree draws every call as a box. Each call’s box is connected to the boxes of the calls it makes, below it. The top box is the first call; boxes with no calls below them are base cases. Reading the boxes level by level shows how much work there is.

Two calls per call: Fibonacci

The Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, … are defined by fib(0) = 0, fib(1) = 1, fib(n) = fib(n − 1) + fib(n − 2). Written directly as recursion, every call (except the base cases) makes two calls:

int calls = 0;

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

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

Output

fib(5) = 5, calls = 15

The number of calls C(n) satisfies C(n) = 1 + C(n − 1) + C(n − 2), with C(0) = C(1) = 1: C(4) = 9, C(5) = 15, C(6) = 25. It grows almost as fast as doubling, because the same values are recomputed again and again (fib(3) is computed twice inside fib(5)).

Counting calls and output

To count calls: draw the tree, or write a counting rule like C(n) = 1 + (calls made by the recursive part) and fill a table from small n upwards. Each call’s printf runs once, so the number of printed items equals the number of calls that reach that printf.

void g(int n)
{
    if (n <= 0)
        return;
    g(n - 1);
    printf("%d ", n);
    g(n - 1);
}

int main(void)
{
    g(3);
    printf("\n");
    return 0;
}

Output

1 2 1 3 1 2 1

g(n) prints 2^n^ − 1 numbers: P(n) = 2P(n − 1) + 1, P(0) = 0 (Lesson 0.2.2’s doubling sum).

Depth vs number of calls

Depth is the number of levels in the drawing (the longest chain from the top box down); the number of calls is the number of boxes. fib(5) has 15 calls but depth only 5 (fib(5) → fib(4) → fib(3) → fib(2) → fib(1)).

4 · Visual

Recursion tree of fib(4): 9 calls (boxes). Green boxes are base cases. fib(2) is computed twice — the source of the waste.

Recursion tree of g(3) (g calls g(n-1), prints n, calls g(n-1)):

                     g(3)
            /         |         \
         g(2)      print 3      g(2)
        /  |  \                /  |  \
     g(1) p2  g(1)          g(1) p2  g(1)
    / | \     / | \        / | \     / | \
  g0 p1 g0  g0 p1 g0     g0 p1 g0  g0 p1 g0

 printed left to right: 1 2 1 3 1 2 1     (2^3 - 1 = 7 numbers)

Reading the prints in the order they happen gives the output.

5 · Worked Examples

Example 1 Easy

What does this print?

void p(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);     /* before the call: on the way down */
    p(n - 1);
    printf("%d ", n);     /* after the call: on the way back up */
}

int main(void)
{
    p(3);
    printf("\n");
    return 0;
}

Solution

Down: 3 2 1. Up: 1 2 3.

Output

3 2 1 1 2 3

Example 2 Medium

How many calls does fib(6) make in the program above (counting the first call)?

Solution

C(0) = C(1) = 1; C(2) = 1 + 1 + 1 = 3; C(3) = 1 + 3 + 1 = 5; C(4) = 9; C(5) = 15; C(6) = 1 + 15 + 9 = 25.

Example 3 GATE

What does this print, and how many calls of h are made (including those with n < 1)?

void h(int n)
{
    if (n < 1)
        return;
    h(n - 2);
    printf("%d ", n);
    h(n - 1);
}

int main(void)
{
    h(3);
    printf("\n");
    return 0;
}

Solution

h(3): h(1) first → [h(−1) returns, print 1, h(0) returns]; print 3; then h(2) → [h(0) returns, print 2, h(1) → [h(−1), print 1, h(0)]]. Output: 1 3 2 1. Calls: H(n) = 1 + H(n − 2) + H(n − 1) with H(n) = 1 for n < 1: H(1) = 3, H(2) = 5, H(3) = 1 + 3 + 5 = 9.

Output

1 3 2 1

6 · GATE Traps

⚠️

• Printing after the recursive call reverses the order.
• Count calls including the base-case calls (the leaves of the tree).
• Depth ≠ number of calls.
• Two recursive calls per call can make the number of calls grow exponentially.
• With two calls, the second call starts only after the first has completely finished (the whole left part of the tree first).

8 · Memory Hook

🧠

“Down the stairs, then back up.” Work before the call happens on the way down, work after it on the way up. Two calls per step and the stairs become a branching family tree.

9 · Connect the Dots

Lesson 2.1.1 traced one chain of calls; recursion trees show branching calls and let us count them. With the tracing tools in place, the next lesson answers: what are the classic recursive programs GATE expects you to know (factorial, Fibonacci, the greatest common divisor, power, a famous disk-moving puzzle), and why does each one stop?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markOrder

What does this print?

void g(int n)
{
    if (n <= 0)
        return;
    g(n - 1);
    printf("%d ", n);
    g(n - 1);
}

int main(void)
{
    g(3);
    printf("\n");
    return 0;
}

• (A) 1 2 1 3 1 2 1
• (B) 3 2 2 1 1 1 1
• (C) 1 2 3
• (D) 3 2 1 1 2 3

Q2NAT2 marksCounting calls

Using C(n) = 1 + C(n − 1) + C(n − 2) with C(0) = C(1) = 1, how many calls does fib(7) make?

Numerical answer: ________

Q3MCQ2 marksOutput

What does this print?

void h(int n)
{
    if (n < 1)
        return;
    h(n - 2);
    printf("%d ", n);
    h(n - 1);
}

int main(void)
{
    h(3);
    printf("\n");
    return 0;
}

• (A) 3 1 2 1
• (B) 1 3 2 1
• (C) 1 2 3
• (D) 1 3 1 2

Q4NAT1 markPrints

How many numbers does g(5) print, where g prints n between two calls of g(n − 1) and g(0) prints nothing?

Numerical answer: ________

Q5MSQ1 markTrees

In a recursion tree, which are true?

• (A) The top box is the first call.
• (B) The boxes with no calls below them are base cases.
• (C) Each box is one call.
• (D) The number of boxes equals the recursion depth.

11 · Rule Card

• Before the call: runs going down (call order). After the call: runs coming back (reverse order).
• Recursion tree: one box per call; base cases at the bottom; top = first call.
• Calls with two branches: C(n) = 1 + C(left) + C(right); fill a table bottom-up.
• fib calls: 1, 1, 3, 5, 9, 15, 25, 41 for n = 0…7.
• Two calls of n − 1 each: 2ⁿ − 1 prints; depth n.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

recursion treenumber of callswork before / after the recursive callFibonacci (recursive)repeated subproblems

13 · Answer Vault