Fibonacci Using Recursion in DSA Python

Mental Model

Each Fibonacci number is the sum of the two before it, and recursion breaks this down by calling itself with smaller numbers until it reaches the base cases.

Analogy: Imagine climbing stairs where to reach step n, you first need to know how many ways to reach step n-1 and step n-2, and you keep asking smaller steps until you reach the bottom steps you already know.

fib(n)
  /    \
fib(n-1) fib(n-2)
  / \      / \
... ...  ... ...

Dry Run Walkthrough

Input: Calculate fibonacci(4)

Goal: Find the 4th Fibonacci number using recursion

Step 1: Call fibonacci(4), which calls fibonacci(3) and fibonacci(2)

fib(4) -> fib(3) + fib(2)

Why: We break the problem into smaller Fibonacci calculations

Step 2: Call fibonacci(3), which calls fibonacci(2) and fibonacci(1)

fib(4) -> (fib(2) + fib(1)) + fib(2)

Why: Continue breaking down until base cases

Step 3: Call fibonacci(2), which calls fibonacci(1) and fibonacci(0)

fib(4) -> ((fib(1) + fib(0)) + fib(1)) + fib(2)

Why: Keep breaking down to base cases

Step 4: Return base cases: fibonacci(1) = 1, fibonacci(0) = 0

fib(4) -> ((1 + 0) + 1) + fib(2)

Why: Base cases stop recursion and provide known values

Step 5: Calculate fibonacci(2) again as fibonacci(1) + fibonacci(0) = 1 + 0 = 1

fib(4) -> ((1 + 0) + 1) + 1

Why: Calculate remaining parts to sum up

Step 6: Sum all parts: (1 + 0) + 1 + 1 = 3

fib(4) = 3

Why: Final result is the 4th Fibonacci number

Result:

fib(4) = 3

Annotated Code

DSA Python

def fibonacci(n: int) -> int:
    if n == 0:
        return 0  # base case: fib(0) = 0
    if n == 1:
        return 1  # base case: fib(1) = 1
    return fibonacci(n - 1) + fibonacci(n - 2)  # recursive step

# Driver code to test fibonacci(4)
result = fibonacci(4)
print(result)

if n == 0:

check base case for zero

if n == 1:

check base case for one

return fibonacci(n - 1) + fibonacci(n - 2)

recursive call to sum previous two Fibonacci numbers

Output

3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, leading to exponential growth

Space: O(n) due to the maximum depth of the recursion stack being n

vs Alternative: Iterative approach is O(n) time and O(1) space, which is much more efficient than this exponential recursive method

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Python

if n == 0:

n = 1

Returns 1 immediately as base case

DSA Python

if n == 1:

negative n

No handling; recursion will continue indefinitely or error

DSA Python

No guard for negative input in code

When to Use This Pattern

When a problem asks for a sequence where each term depends on previous terms, and you see repeated calls with smaller inputs, recursion with base cases is a natural pattern to try.

Common Mistakes

Mistake: Forgetting base cases causes infinite recursion
Fix: Always include base cases for n=0 and n=1 to stop recursion

Mistake: Calling fibonacci(n-1) + fibonacci(n-2) without return
Fix: Use return to pass the sum back up the call stack

Summary

Calculates the nth Fibonacci number by adding the two previous Fibonacci numbers recursively.

Use when you want a simple, clear way to define Fibonacci numbers, especially for learning recursion.

The key is breaking the problem into smaller parts until reaching simple base cases.

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