Following a recursive call by hand
Recursion becomes obvious once you draw the calls going down and the answers coming back up. Most confusion is about what happens on the way back.
After this lesson
You should be able to
- Trace a recursive call, writing each level's argument and return value.
- Explain the difference between work done before and after the recursive call.
- Write factorial and Fibonacci recursively.
Down, then back up
factorial(4) cannot answer until factorial(3) does, which waits for factorial(2), and so on down to the base case. Only when factorial(1) returns 1 does the chain unwind, each level multiplying and returning upward.
Writing the trace as two columns — the calls going down and the values coming back — makes it concrete. The answer is built on the way back, not on the way down.
factorial(4)
-> 4 * factorial(3)
-> 3 * factorial(2)
-> 2 * factorial(1)
-> 1 base case
<- 2 * 1 = 2
<- 3 * 2 = 6
<- 4 * 6 = 24Before or after changes everything
Print before the recursive call and you see 3, 2, 1. Print after it and you see 1, 2, 3 — the same function, the same recursion, opposite output. Work placed before happens on the way down; work placed after happens on the way back.
That single choice is how you reverse a sequence with no extra array. It is worth running both versions once and watching the difference.
void down(int n)
{
if (n == 0) return;
printf("%d ", n); /* before: 3 2 1 */
down(n - 1);
}
void up(int n)
{
if (n == 0) return;
up(n - 1);
printf("%d ", n); /* after: 1 2 3 */
}Fibonacci, and why it is slow
Fibonacci has two base cases and two recursive calls. It is a faithful translation of the definition, but each call splits into two, so the work roughly doubles with every step — fib(40) makes over a billion calls.
The reason is repetition: fib(5) computes fib(3) twice, fib(2) three times, and so on. A loop computes each value once. This is the clearest example of recursion being elegant and still the wrong tool.
Try it yourself
Trace factorial(5) on paper, then write both a recursive and a loop version and compare their structure.
Need a hint?
The trace has five levels going down and five multiplications coming back.
Check the worked solution
Both give 120. The recursive version mirrors the definition and the loop version mirrors the computation — the loop uses one variable and constant memory, while the recursion holds five paused calls at its deepest point. For factorial the loop is the better engineering choice; the recursion is the better teaching one.
#include <stdio.h>
long long fact_rec(int n)
{
if (n <= 1) return 1;
return n * fact_rec(n - 1);
}
long long fact_loop(int n)
{
long long product = 1;
for (int i = 2; i <= n; i++)
product *= i;
return product;
}
int main(void)
{
printf("%lld %lld\n", fact_rec(5), fact_loop(5)); /* 120 120 */
return 0;
}Quick check
void f(int n){ if(n==0) return; f(n-1); printf("%d ", n); } — what does f(3) print?
Why this lesson exists
Syllabus mapping
Tracing a Recursive Function · Recursive Mathematical Functions
Maps to course outcomes CO1, CO4.