- 2070 Magh · 3 marks
Tail and non-tail recursion
Short answer
Tail recursion: the recursive call is the last operation, so the stack frame can be reused and the recursion optimized into a loop (e.g., factorial with accumulator). Non-tail recursion: work remains after the call (e.g., n * fact(n-1)), so the full call stack is needed.
What is tail and non-tail recursion with example?
Tail recursion: a recursive call is a tail call if it is the very last thing the function does. Nothing is left to do after the call returns, so the result of the inner call is the result of the function. A compiler can reuse the same stack frame, which turns the recursion into a loop.
/* tail recursive: factorial with accumulator */
int fact(int n, int acc) {
if (n == 0) return acc;
return fact(n - 1, n * acc); /* last action is the call */
}
fact(4,1) → fact(3,4) → fact(2,12) → fact(1,24) → fact(0,24) = 24. No pending multiplication stays on the stack.
Non-tail recursion: some work is still pending after the recursive call returns, so every frame must stay on the stack until the calls unwind.
/* non-tail recursive factorial */
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1); /* multiplication after the call */
}
fact(4) = 4 × fact(3) = 4 × (3 × (2 × (1 × 1))). Four frames wait for the result. Tower of Hanoi, tree traversals and Fibonacci fib(n-1)+fib(n-2) are also non-tail.
| Point | Tail recursion | Non-tail recursion |
|---|---|---|
| Work after the call | none | yes (multiply, add, print) |
| Stack space | O(1) with optimisation | O(n) |
| Conversion to loop | easy | needs an explicit stack |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Is recursion slow; recursive vs non-recursive · Data Structure and Algorithm, chapter 5