Past exam question: 2072 Ashwin (Regular), Q7
Open in the Padhaiko appDo you think recursive function is slow? Compare recursive and non-recursive functions. Draw recursion tree for Tower of Hanoi assuming 4 disks.
Solution
Why Recursive Functions Can Be Slower: Yes—compared to an equivalent iterative loop, a recursive function typically runs slower because every recursive call incurs function-call overhead: pushing an activation record (arguments, local variables, return address) onto the call stack, jumping, and popping it upon return. Naive tree-recursive functions (like naive fib(n)) can also recompute identical subproblems exponentially many times.
Recursive vs. Non-Recursive (Iterative) Functions:
| Aspect | Recursive Function | Non-Recursive (Iterative) Function |
|---|---|---|
| Control Flow | Self-calls down to base case | for / while loop until termination condition |
| Memory Usage | stack frames | loop variables |
| Speed | Slower per step due to call/return overhead | Faster; no stack-frame allocation overhead |
| Readability | Compact and natural for trees, TOH, DFS, quicksort | Longer or requires an explicit manual stack for tree/graph tasks |
Recursion Tree for TOH(4, A, B, C) ( Moves):
TOH(4,A,B,C)
/ | \
TOH(3,A,C,B) [A->C] TOH(3,B,A,C)
/ | \ / | \
TOH(2,A,B,C) [A->B] TOH(2,C,A,B) TOH(2,B,C,A) [B->C] TOH(2,A,B,C)
/ | \ / | \ / | \ / | \
T(1) A->C T(1) T(1) C->B T(1) T(1) B->A T(1) T(1) A->C T(1)
A->B B->C C->A A->B B->C C->A A->B B->C
(Each leaf T(1) represents the base-case single-disk move printed directly beneath it; total moves = .)
Recursive functions are generally slower than loops due to call-stack frame overhead (and potential duplicate subproblems). The 4-disk TOH(4, A, B, C) recursion tree has depth 4 and executes moves.