PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q5

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Recursion

Question

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:

  1. Stack Memory Overhead: Each active call allocates a frame on the call stack ( space); deep recursion risks stack overflow.
  2. Function-Call Overhead: Repeated stack frame pushes/pops make recursion slower than equivalent loops.
  3. 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 .

All past exam questions for Data Structure and Algorithms