Fibonacci Using Recursion in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in a recursive Fibonacci function?

The base case returns the first two Fibonacci numbers directly: fib(0) = 0 and fib(1) = 1. This stops the recursion from continuing infinitely.

beginner

Explain how recursion works in the Fibonacci sequence calculation.

Recursion breaks the problem into smaller parts by calling the Fibonacci function for (n-1) and (n-2) until it reaches the base cases. Then it adds those results to get fib(n).

intermediate

What is the time complexity of the naive recursive Fibonacci algorithm?

The time complexity is exponential, specifically O(2^n), because it recalculates the same Fibonacci numbers many times.

beginner

Write the recursive formula for Fibonacci numbers.

fib(n) = fib(n-1) + fib(n-2) with base cases fib(0) = 0 and fib(1) = 1.

intermediate

Why is recursion not efficient for large Fibonacci numbers without optimization?

Because it repeats calculations for the same values many times, leading to a lot of unnecessary work and slow performance.

What does the base case in Fibonacci recursion return for fib(0)?

A 0

B 1

C Undefined

D fib(1)

The base case fib(0) returns 0 to stop recursion.

Which of these is the recursive call in Fibonacci calculation?

A fib(n) = fib(n-1) + fib(n-2)

B fib(n) = n + fib(n-1)

C fib(n) = fib(n-1) * fib(n-2)

D fib(n) = fib(n-1) - fib(n-2)

The Fibonacci number is the sum of the two previous Fibonacci numbers.

What is the main problem with naive recursive Fibonacci?

A It uses too much memory

B It recalculates values multiple times

C It never reaches base case

D It only works for even numbers

Naive recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

What is the output of fib(3) using recursion?

A 1

B 3

C 2

D 5

fib(3) = fib(2) + fib(1) = 1 + 1 = 2.

Which of these is NOT a base case for Fibonacci recursion?

A fib(0) = 0

B fib(1) = 1

C fib(2) = 1

D fib(3) = 2

Only fib(0) and fib(1) are base cases; fib(3) is calculated recursively.

Describe how the Fibonacci sequence is calculated using recursion.

Think about how the function calls itself with smaller numbers until it reaches the simplest cases.

Explain why naive recursion for Fibonacci is inefficient and how it can be improved.

Consider what happens when the function calls itself many times for the same input.

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