PadhaikoAll subjects

Past exam question: 2064 Jestha, Q4

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

What is mean by recursion tree? Write recursive and iterative algorithms for Fibonacci number and compare and contrast the efficiency of two algorithms. Can every recursive problem be solved iteratively?

Solution

Meaning of Recursion Tree: A recursion tree is a tree diagram visualizing every recursive function call generated during execution: each node represents a subproblem invocation, edges point from caller to recursive sub-calls, and leaves represent base cases.

Recursive vs. Iterative Fibonacci Algorithms (F(0)=0, F(1)=1):

Algorithm FIB_REC(n):
1. If n <= 1: Return n
2. Return FIB_REC(n - 1) + FIB_REC(n - 2)

Algorithm FIB_ITER(n):
1. If n <= 1: Return n
2. a = 0, b = 1
3. For i = 2 to n:
       c = a + b
       a = b
       b = c
4. Return b

Can Every Recursive Problem Be Solved Iteratively? Yes. Every recursive algorithm can be transformed into an equivalent iterative algorithm by explicitly simulating the system call stack with an explicit user-managed stack data structure and a while loop (though tail recursion converts into a simple loop with space).

Answer:

A recursion tree traces all nested sub-calls down to base cases. Recursive Fibonacci runs in time and stack space, whereas iterative Fibonacci runs in time and space. Yes, every recursive problem can be solved iteratively using loops (and an explicit stack where needed).

All past exam questions for Data Structure and Algorithms