Fibonacci Using Recursion in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Call

What is the output of the following code snippet?

DSA Python

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(5))

A 13

B 8

C 3

D 5

💡 Hint

Remember the Fibonacci sequence starts 0, 1, 1, 2, 3, 5...

fib(5) returns the 5th Fibonacci number which is 5 (0-based index: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5).

❓ Predict Output

intermediate

Output of Recursive Fibonacci with Print

What will be printed when this code runs?

DSA Python

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

for i in range(4):
    print(fib(i), end=' -> ')
print('null')

A 1 -> 1 -> 2 -> 3 -> null

B 0 -> 1 -> 1 -> 2 -> null

C 0 -> 1 -> 2 -> 3 -> null

D 1 -> 2 -> 3 -> 5 -> null

💡 Hint

Check the Fibonacci values for 0, 1, 2, 3

fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, so the printed sequence is 0 -> 1 -> 1 -> 2 -> null.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci

What error will this code produce when run?

DSA Python

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-3)

print(fib(4))

A 0

B TypeError: unsupported operand type(s)

C RecursionError: maximum recursion depth exceeded

D 3

💡 Hint

Check the recursive calls and base cases carefully.

The function calls fib(n-3) but does not handle n < 0, causing infinite recursion and eventually a RecursionError.

❓ Predict Output

advanced

Output of Memoized Fibonacci Recursive Function

What is the output of this memoized Fibonacci function?

DSA Python

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(6))

A 8

B 13

C 5

D 21

💡 Hint

Memoization stores results to avoid repeated work.

fib(6) is 8 in the Fibonacci sequence starting with 0,1.

🧠 Conceptual

expert

Time Complexity of Recursive Fibonacci

What is the time complexity of the naive recursive Fibonacci function without memoization?

A O(2^n)

B O(n)

C O(n^2)

D O(log n)

💡 Hint

Consider how many calls are made for each fib(n).

Each call to fib(n) makes two calls to fib(n-1) and fib(n-2), leading to exponential growth.

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the square of the previous number

B. Each number is the product of the two preceding numbers

C. Each number is the difference of the two preceding numbers

D. Each number is the sum of the two preceding numbers

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence is defined such that each number is the sum of the two numbers before it.

2. Step 2: Relate to recursion

   Recursion calculates this by calling the function for the two previous numbers and adding their results.

3. Final Answer:

   Each number is the sum of the two preceding numbers -> Option D

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds two previous numbers, not multiply or subtract [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing difference with sum
• Assuming Fibonacci squares previous number

2. Which of the following is the correct base case syntax for a recursive Fibonacci function in Python?

easy

A. if n == 0 or n == 1: return n

B. if n < 0: return 0

C. if n == 2: return 1

D. if n == 1: return 0

Solution

1. Step 1: Identify base cases for Fibonacci

   Fibonacci sequence starts with 0 at position 0 and 1 at position 1, so base cases are n == 0 and n == 1.

2. Step 2: Check syntax correctness

   The correct syntax returns n when n is 0 or 1, matching the base cases.

3. Final Answer:

   if n == 0 or n == 1: return n -> Option A

4. Quick Check:

   Base cases return n for 0 or 1 [OK]

Hint: Base cases return n when n is 0 or 1 [OK]

Common Mistakes:

• Using wrong base case values
• Returning 0 for n == 1
• Missing base case for n == 0

3. What is the output of the following code?

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

print(fib(4))

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0)

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1; fib(2)=1+0=1; fib(3)=1+1=2; fib(4)=2+1=3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Calculate fib(n-1) + fib(n-2) stepwise [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong values for fib(2) or fib(3)
• Forgetting base cases

4. Find the error in this recursive Fibonacci function:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) - fib(n-2)

medium

A. The base cases are incorrect

B. The recursive step uses subtraction instead of addition

C. The function lacks a return statement

D. The function will cause infinite recursion

Solution

1. Step 1: Check base cases

   Base cases for n == 0 and n == 1 are correct and return proper values.

2. Step 2: Analyze recursive step

   The recursive step uses subtraction (fib(n-1) - fib(n-2)) instead of addition, which is incorrect for Fibonacci.

3. Final Answer:

   The recursive step uses subtraction instead of addition -> Option B

4. Quick Check:

   Recursive step must add previous two values [OK]

Hint: Fibonacci recursion adds, never subtracts previous two [OK]

Common Mistakes:

• Using subtraction in recursive step
• Misunderstanding base cases
• Missing return keyword

5. How many total calls are made when computing fib(5) using the naive recursive Fibonacci function?

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

hard

A. 15

B. 9

C. 7

D. 10

Solution

1. Step 1: Count calls for fib(5)

   fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1), etc.

2. Step 2: Calculate total calls

   Total calls = 15 (including repeated calls for fib(3), fib(2), fib(1), fib(0)) as the recursion tree expands.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Naive recursion calls grow exponentially; fib(5) = 15 calls [OK]

Hint: Count all calls in recursion tree for fib(n) [OK]

Common Mistakes:

• Counting only unique calls
• Ignoring repeated calls in recursion
• Underestimating exponential growth