Fibonacci Using Recursion in DSA Python - Execution Trace

Concept Flow - Fibonacci Using Recursion

Call fibonacci(n)

↓

Is n <= 1?

Yes→Return n

No↓

Call fibonacci(n-1)

↓

Call fibonacci(n-2)

↓

Add results of fibonacci(n-1) + fibonacci(n-2)

↓

Return sum

↓

End call for fibonacci(n)

The function calls itself with smaller values until it reaches the base case, then returns and adds results back up.

Execution Sample

DSA Python

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

print(fibonacci(4))

Calculates the 4th Fibonacci number using recursion.

Execution Table

Step	Call	Arguments	Return Value	Stack Depth	Action
1	fibonacci	4	-	1	Check if 4 <= 1 (No), call fibonacci(3) and fibonacci(2)
2	fibonacci	3	-	2	Check if 3 <= 1 (No), call fibonacci(2) and fibonacci(1)
3	fibonacci	2	-	3	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
4	fibonacci	1	1	4	Base case reached, return 1
5	fibonacci	0	0	4	Base case reached, return 0
6	fibonacci	2	1	3	Return 1 + 0 = 1
7	fibonacci	1	1	3	Base case reached, return 1
8	fibonacci	3	2	2	Return 1 + 1 = 2
9	fibonacci	2	-	2	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
10	fibonacci	1	1	3	Base case reached, return 1
11	fibonacci	0	0	3	Base case reached, return 0
12	fibonacci	2	1	2	Return 1 + 0 = 1
13	fibonacci	4	3	1	Return 2 + 1 = 3
14	-	-	-	-	Execution complete, fibonacci(4) = 3

💡 All recursive calls resolved, final result returned.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 8	After Step 13	Final
n	4	4	3	2	2	3	4	4
Return Value	-	-	-	-	1	2	3	3
Stack Depth	1	1	2	3	3	2	1	1

Key Moments - 3 Insights

Why does fibonacci(2) get called multiple times?

Because each call to fibonacci(n) calls fibonacci(n-1) and fibonacci(n-2) independently, causing repeated calls as shown in steps 3, 6, 9, and 12.

Why do we return n when n <= 1?

This is the base case stopping recursion. Steps 4, 5, 7, 10, and 11 show returning n directly to avoid infinite calls.

How does the stack depth change during recursion?

Stack depth increases with each recursive call (steps 1 to 4) and decreases as calls return (steps 6, 8, 13), shown clearly in the 'Stack Depth' column.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value of fibonacci(3) at step 8?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Return Value' column at step 8 for fibonacci(3).

At which step does the recursion reach the deepest stack level?

A Step 4

B Step 1

C Step 13

D Step 14

💡 Hint

Look at the 'Stack Depth' column to find the maximum value.

If we change the input to fibonacci(3), what would be the return value at the final step?

A 3

B 1

C 2

D 5

💡 Hint

Refer to the return value of fibonacci(3) in the execution table at step 8.

Concept Snapshot

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

- Base case: n <= 1 returns n
- Recursive calls: fibonacci(n-1) and fibonacci(n-2)
- Stack grows with calls, unwinds with returns

Full Transcript

The Fibonacci function uses recursion by calling itself with smaller numbers until it reaches the base case where n is 0 or 1. At that point, it returns n directly. Each call waits for the results of fibonacci(n-1) and fibonacci(n-2), adds them, and returns the sum. The stack depth increases as calls go deeper and decreases as they return. This causes repeated calls for the same values, like fibonacci(2), which happens multiple times. The final result for fibonacci(4) is 3.

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