Fibonacci Using Recursion in DSA C++ - 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

The function calls itself with smaller values until it reaches the base case, then returns sums back up the call stack.

Execution Sample

DSA C++

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}

// Call fibonacci(4)

Calculates the 4th Fibonacci number by recursively summing previous two Fibonacci numbers.

Execution Table

Step	Call	Arguments	Return Value	Stack Depth	Action
1	fibonacci	4	pending	1	Start call fibonacci(4)
2	fibonacci	3	pending	2	Call fibonacci(3) from fibonacci(4)
3	fibonacci	2	pending	3	Call fibonacci(2) from fibonacci(3)
4	fibonacci	1	1	4	Base case n=1, return 1
5	fibonacci	0	0	4	Base case n=0, return 0
6	fibonacci	2	1	3	Return 1 + 0 = 1 to fibonacci(3)
7	fibonacci	1	1	3	Base case n=1, return 1
8	fibonacci	3	2	2	Return 1 + 1 = 2 to fibonacci(4)
9	fibonacci	2	pending	2	Call fibonacci(2) from fibonacci(4)
10	fibonacci	1	1	3	Base case n=1, return 1
11	fibonacci	0	0	3	Base case n=0, return 0
12	fibonacci	2	1	2	Return 1 + 0 = 1 to fibonacci(4)
13	fibonacci	4	3	1	Return 2 + 1 = 3, end call

💡 All recursive calls resolved, final result fibonacci(4) = 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 8	After Step 13
n	4	3	2	2	3	4
Return Value	pending	pending	pending	1	2	3
Stack Depth	1	2	3	3	2	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) separately, causing repeated calls as seen in steps 3 and 9.

Why do we return n immediately when n <= 1?

This is the base case stopping recursion, as shown in steps 4, 5, 7, 10, and 11, preventing infinite calls.

How does the stack depth change during recursion?

Stack depth increases with each recursive call and decreases when returning, as tracked in variable_tracker and visible in execution_table steps.

Visual Quiz - 3 Questions

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

A 2

B 1

C 3

D Pending

💡 Hint

Check the 'Return Value' column at step 8 in the execution_table.

At which step does the recursion start to return values back up the call stack?

A Step 9

B Step 6

C Step 4

D Step 13

💡 Hint

Look for the first step where 'Return Value' is not pending in execution_table.

If we change the input to fibonacci(3), how many total calls will be made?

A 3

B 5

C 4

D 6

💡 Hint

Count calls for fibonacci(3) by tracing steps 2 to 8 in execution_table.

Concept Snapshot

Fibonacci Using Recursion:
- Base case: if n <= 1, return n
- Recursive case: return fibonacci(n-1) + fibonacci(n-2)
- Calls build a stack until base case reached
- Results return back up summing to final answer
- Simple but inefficient due to repeated calls

Full Transcript

This visualization traces the recursive calculation of the Fibonacci number for n=4. The function calls itself with smaller values until it reaches the base case where n is 0 or 1. At each base case, it returns the value immediately. Then, the calls return their sums back up the call stack. The stack depth increases with each call and decreases as calls return. The execution table shows each call, its arguments, return values, and stack depth. Key moments include understanding repeated calls, base case importance, and stack depth changes. The visual quiz tests understanding of return values and call counts.

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 sum of the two preceding numbers starting from 0 and 1

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

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

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.

2. Step 2: Relate to recursion

   Recursion calls the function for the two previous numbers and adds their results to get the current number.

3. Final Answer:

   Each number is the sum of the two preceding numbers starting from 0 and 1 -> Option B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds last two numbers recursively [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or squares with Fibonacci
• Ignoring the base cases 0 and 1

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

easy

A. if (n == 1) return 0; if (n == 2) return 1;

B. if (n <= 2) return n;

C. if (n == 0) return 0; if (n == 1) return 1;

D. if (n == 0) return 1; if (n == 1) return 1;

Solution

1. Step 1: Identify correct Fibonacci base cases

   Fibonacci sequence starts with 0 at position 0 and 1 at position 1, so base cases must return these values.

2. Step 2: Match base cases to code

   if (n == 0) return 0; if (n == 1) return 1; correctly returns 0 for n=0 and 1 for n=1, matching Fibonacci definition.

3. Final Answer:

   if (n == 0) return 0; if (n == 1) return 1; -> Option C

4. Quick Check:

   Base cases match Fibonacci start [OK]

Hint: Base cases: 0 returns 0, 1 returns 1 [OK]

Common Mistakes:

• Using wrong base values like 1 for n=0
• Returning n for n <= 2 which is incorrect
• Confusing base cases with general recursive step

3. What is the output of the following C++ code?

int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-1) + fib(n-2);
}

int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Calculate fib(5) using recursion

   fib(5) = fib(4) + fib(3). Calculate fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), and so on until base cases.

2. Step 2: Evaluate values step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Calculating fib(5) as 8 or 13 by mistake
• Confusing index starting point
• Skipping base cases in calculation

4. Identify the error in this recursive Fibonacci function:

int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-2) + fib(n-1);
}

medium

A. No error, function is correct

B. The recursive calls are in wrong order; should be fib(n-1) + fib(n-2)

C. Base cases are incorrect

D. Missing return type in function

Solution

1. Step 1: Check base cases

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

2. Step 2: Check recursive step

   fib(n-2) + fib(n-1) equals fib(n-1) + fib(n-2) because addition is commutative. Function computes correct values. No error.

3. Final Answer:

   No error, function is correct -> Option A

4. Quick Check:

   Addition commutative, no error [OK]

Hint: Addition order irrelevant, commutative [OK]

Common Mistakes:

• Thinking recursive call order must be strictly n-1 first
• Assuming reversed order changes the result
• Overlooking commutativity of addition

5. How many times is the function fib called when computing fib(4) using the recursive function below?

int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-1) + fib(n-2);
}

hard

A. 5

B. 7

C. 15

D. 9

Solution

1. Step 1: Trace calls for fib(4)

   fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0).

2. Step 2: Count total calls

   Calls: fib(4), fib(3), fib(2), fib(1), fib(2), fib(1), fib(0), fib(1), fib(0) = 9 calls total.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Count recursive calls carefully = 9 [OK]

Hint: Count each fib call including duplicates [OK]

Common Mistakes:

• Counting only unique calls
• Ignoring repeated calls for same n
• Underestimating recursion tree size