Past exam question: 2066 Bhadra (Regular / Back), Q5
Open in the Padhaiko appQuestion
Explain recursion with its disadvantages? Draw the recursive tree diagram for the fibonacci sequence :fib(5).
Solution
Recursion and Its Disadvantages: Recursion is a technique where a function calls itself on smaller subproblems down to a base case. Disadvantages:
- Stack Memory Overhead: Each active call allocates a frame on the call stack ( space); deep recursion risks stack overflow.
- Function-Call Overhead: Repeated stack frame pushes/pops make recursion slower than equivalent loops.
- Redundant Recomputation: Tree-recursive problems like naive Fibonacci recompute overlapping subproblems exponentially ( calls).
Recursion Tree Diagram for fib(5) (fib(0) = 0, fib(1) = 1):
fib(5) [5]
/ \
fib(4) [3] fib(3) [2]
/ \ / \
fib(3) [2] fib(2) [1] fib(2) [1] fib(1) [1]
/ \ / \ / \
fib(2)[1] fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Total function calls = , returning fib(5) = 5. (Under 1-based indexing fib(1)=1, fib(2)=1, fib(5) = 5 with calls rooted at fib(5) -> fib(4), fib(3) down to fib(2), fib(1).)
Answer:
Recursion solves problems via self-invocation down to a base case, but incurs call-stack memory overhead, slower execution, and redundant recomputation. The recursion tree for fib(5) (with fib(0)=0, fib(1)=1) makes 15 calls and returns .