Recursion

ACompressed recap

🧾

A recursive function has a base case and a recursive case that moves towards it; each call has its own frame, and missing progress means stack overflow. Work before the call runs going down, work after it coming back up. Recursion trees show every call: fib makes 1, 1, 3, 5, 9, 15, 25… calls; two calls of n − 1 give 2ⁿ − 1 calls. Classics: factorial, Fibonacci, gcd(b, a % b), power by halving, Hanoi 2ⁿ − 1, digits via % 10 and / 10. To find values, write the recurrence and fill a table; with static or global variables, trace calls in order instead.

BMerged rule card

2.1.1 Base case and recursive case; tracing calls on the stack

• Recursive function = base case (no call) + recursive case (smaller input).
• Every input must eventually reach a base case, or the stack overflows.
• Each call has its own frame: own parameters and locals.
• Calls go down to the base case; results come back up.
• Depth = longest chain of active calls (sum(n): n + 1).

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

• 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.

2.1.3 Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

• n! = n·(n − 1)!, 0! = 1: n calls.
• fib(n) = fib(n − 1) + fib(n − 2): exponential calls; loop is linear.
• gcd(a, b) = gcd(b, a % b), gcd(a, 0) = a.
• xⁿ by halving: ≈ log₂ n calls.
• Hanoi: M(n) = 2M(n − 1) + 1 = 2ⁿ − 1; largest disk 1 move, smallest 2ⁿ⁻¹.
• Digits: n % 10 last digit, n / 10 rest. Arrays: a[n − 1] + rest, or *a + (a + 1).

2.1.4 Computing what a recursive function returns via its recurrence; static and global variables inside recursion

• Write the recurrence: f(n) in terms of f(smaller) + base values copied exactly from the code.
• Pure functions: fill a table bottom-up.
• Known forms: f(n − 1) + n → n(n + 1)/2; 2f(n − 1) + 1 → 2ⁿ − 1; f(n/2) + 1 → ⌊log₂ n⌋ + 1.
• Static/global inside recursion: shared by all calls, initialized once; trace calls in execution order.
• return f(…) passes the base-case value up unchanged.

CInterleaved GATE-style questions

Q1MCQ1 markOrder

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;
}

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

Q2NAT2 marksCalls

How many calls does recursive fib(6) make (fib(0), fib(1) are base cases)?

Numerical answer: ________

Q3NAT1 markHanoi

In Tower of Hanoi with 7 disks, how many times does the smallest disk move?

Numerical answer: ________

Q4MCQ2 marksPower

What does this print?

int mults = 0;

long power(long x, int n)
{
    long half;
    if (n == 0)
        return 1;
    half = power(x, n / 2);
    mults++;
    if (n % 2 == 0)
        return half * half;
    mults++;
    return half * half * x;
}

int main(void)
{
    long v = power(3, 13);
    printf("%ld %d\n", v, mults);
    return 0;
}

• (A) 1594323 7
• (B) 1594323 12
• (C) 39 7
• (D) 1594323 13

Q5NAT2 marksRecurrence

For t(n) = t(n − 1) + 2t(n − 2), t(1) = t(2) = 1, what is t(7)?

Numerical answer: ________

Q6MCQ2 marksStatic

What does this print?

int f(int n)
{
    static int r = 0;
    if (n <= 0)
        return 1;
    if (n > 3) {
        r = n;
        return f(n - 2) + 2;
    }
    return f(n - 1) + r;
}

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

• (A) 18
• (B) 12
• (C) 15
• (D) 20

Q7MSQ1 markFacts

Which are true?

• (A) Recursion depth can be much smaller than the number of calls.
• (B) A static local is re-initialized on every recursive call.
• (C) Each recursive call has its own parameters.
• (D) Without a base case, recursion ends with a stack overflow.

Q8MCQ1 markMystery

int g(int n) { if (n < 10) return n; return g(n / 10) + n % 10; } computes:

• (A) the sum of digits
• (B) the number of digits
• (C) the last digit
• (D) n reversed

Q9NAT1 markDepth

What is the maximum recursion depth (frames of f) of f(n) = n * f(n - 2) with base case n ≤ 1, for f(9)?

Numerical answer: ________

DAnswer Vault