5.4Tracing recursion: counting calls and return values
The idea
To count calls or find a return value, draw the call tree. Linear recursion has depth n; two recursive calls per level grow exponentially.
Think of it like this: A family tree: every call is a parent with children; counting the people counts the calls.
Why it exists
GATE asks for the number of calls or the return value of a small recursive function; a clean tree avoids mistakes.
How it works
- Write the first call as the root.
- For each call, write the calls it makes, with their arguments.
- Stop each branch at the base case and write the returned value.
- Combine values upward and count the nodes.
Worked example: fib(4)
fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1); and so on: 9 calls and the result 3.
Now play with it
- →Run Fibonacci call tree and count the lines.
- →Run never shrinks: foo(val--) passes the old value, so you see a stack overflow.
fib(4) makes two recursive calls at every level, so the number of calls grows exponentially. Count the lines in the call tree: 9 calls for fib(4).
1#include <stdio.h>2int fib(int n) {3 if (n < 2) return n;4 return fib(n - 1) + fib(n - 2);5}6int main() {7 printf("%d\n", fib(4));8 return 0;9}
The gold line is the statement about to run.
Call stack (top first)
Output
Call tree so far (indent = recursion depth)
Check yourself
How many calls (including the first) does fib(3) make, with fib(n) = n for n < 2 and fib(n−1) + fib(n−2) otherwise?
Exam notes (the dense version)
Write the calls as a tree. For a linear recursion on n the depth is n. For f(n) = f(n−1) + f(n−2) the number of calls is exponential (Fibonacci-like): calls(n) = calls(n−1) + calls(n−2) + 1. A recursion that does not shrink its argument (such as foo(val--), which passes the old value) never reaches the base case and ends in stack overflow.
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.