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 and sums results back up.

Execution Sample

DSA C

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

This code calculates the nth Fibonacci number by calling itself with n-1 and n-2 until it reaches 0 or 1.

Execution Table

Step	Call Stack (Top)	Current n	Action	Return Value	Stack Depth
1	fibonacci(4)	4	Check if n <= 1 (No), call fibonacci(3)		1
2	fibonacci(3)	3	Check if n <= 1 (No), call fibonacci(2)		2
3	fibonacci(2)	2	Check if n <= 1 (No), call fibonacci(1)		3
4	fibonacci(1)	1	n <= 1 (Yes), return 1	1	4
5	fibonacci(0)	0	n <= 1 (Yes), return 0	0	4
6	fibonacci(2)	2	Return fibonacci(1)+fibonacci(0) = 1+0	1	3
7	fibonacci(1)	1	n <= 1 (Yes), return 1	1	3
8	fibonacci(3)	3	Return fibonacci(2)+fibonacci(1) = 1+1	2	2
9	fibonacci(2)	2	Check if n <= 1 (No), call fibonacci(1)		2
10	fibonacci(1)	1	n <= 1 (Yes), return 1	1	3
11	fibonacci(0)	0	n <= 1 (Yes), return 0	0	3
12	fibonacci(2)	2	Return fibonacci(1)+fibonacci(0) = 1+0	1	2
13	fibonacci(4)	4	Return fibonacci(3)+fibonacci(2) = 2+1	3	1
14	-	-	All calls complete, final result = 3	3	0

💡 Recursion ends when n <= 1, returning n; all calls then return sums up to the original call.

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	1	2	3	3
Stack Depth	0	1	2	3	3	2	1	0

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 for the same n, as seen in steps 3, 6, 9, and 12.

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

Because n=0 or n=1 are the base cases of the Fibonacci sequence, stopping recursion and providing known values, as shown in steps 4, 5, 7, 10, and 11.

How does the call stack depth change during recursion?

The stack depth increases as recursive calls go deeper (steps 1 to 4), then decreases as calls return (steps 6, 8, 13), shown clearly in the Stack Depth column.

Visual Quiz - 3 Questions

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

A 1

B 0

C 2

D Undefined

💡 Hint

Check the Return Value column at step 4 in the execution_table.

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

A Step 1

B Step 6

C Step 4

D Step 14

💡 Hint

Look for the first step where Return Value is filled in the execution_table.

If we call fibonacci(5) instead of fibonacci(4), how would the final return value change?

A It would be 4

B It would be 5

C It would be 3

D It would be 8

💡 Hint

Recall Fibonacci sequence: fibonacci(4) returns 3, fibonacci(5) returns 5.

Concept Snapshot

Fibonacci Using Recursion:
- Base case: if n <= 1, return n
- Recursive case: return fibonacci(n-1) + fibonacci(n-2)
- Calls build up until base case, then sum back up
- Call stack depth grows with n
- Repeated calls cause inefficiency without memoization

Full Transcript

This visualization traces the recursive Fibonacci function for n=4. The function calls itself with smaller values until it reaches the base case where n is 0 or 1, returning n immediately. Each call waits for the results of fibonacci(n-1) and fibonacci(n-2), then sums them and returns the result. The call stack grows as calls nest deeper and shrinks as they return. The execution table shows each step, the current call, action, return values, and stack depth. Key moments include understanding base cases, repeated calls, and stack depth changes. The quiz tests understanding of return values, recursion return timing, and Fibonacci sequence results. This method is simple but inefficient due to repeated calls.

Practice

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

easy

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

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 division 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 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 -> Option A

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds previous two numbers recursively [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or division with addition
• Assuming Fibonacci uses only one previous number

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

easy

A. if (n < 2) return 2;

B. if (n == 0) return 0; else return 1;

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

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

Solution

1. Step 1: Identify base cases for Fibonacci

   Fibonacci sequence starts with 0 and 1 for n=0 and n=1 respectively, so base case returns n when n is 0 or 1.

2. Step 2: Match base case syntax

   The condition if (n <= 1) return n; correctly returns 0 for n=0 and 1 for n=1.

3. Final Answer:

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

4. Quick Check:

   Base case returns n for n=0 or 1 [OK]

Hint: Base case returns n when n is 0 or 1 [OK]

Common Mistakes:

• Returning 2 for base case
• Returning 0 for n=1 incorrectly
• Missing base case leading to infinite recursion

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

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

int main() {
  printf("%d", fib(4));
  return 0;
}

medium

A. 4

B. 3

C. 5

D. 7

Solution

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

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1)+fib(0)) + 1 = (1+0)+1=2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The printf prints the integer 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Trace fib calls down to base cases [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong fib values
• Forgetting base cases

4. Identify the error in this recursive Fibonacci function and select the fix:

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

medium

A. Add base case for n == 1 to return 1

B. Change return 0 to return 1 for n == 0

C. Remove else and just return fib(n-1) + fib(n-2)

D. Change function to iterative instead of recursive

Solution

1. Step 1: Check base cases

   Function only returns 0 for n==0 but misses base case for n==1, causing infinite recursion for n=1.

2. Step 2: Fix by adding base case for n==1

   Adding if (n == 1) return 1; fixes recursion and returns correct Fibonacci values.

3. Final Answer:

   Add base case for n == 1 to return 1 -> Option A

4. Quick Check:

   Both n=0 and n=1 base cases needed [OK]

Hint: Always include base cases for n=0 and n=1 [OK]

Common Mistakes:

• Missing base case for n=1
• Changing base case values incorrectly
• Removing else causing syntax confusion

5. You want to compute the 6th Fibonacci number using recursion but want to avoid repeated calculations. Which approach improves efficiency?

hard

A. Call fib(n-1) twice to ensure correctness

B. Increase the recursion depth limit

C. Use a loop instead of recursion without storing values

D. Use memoization to store and reuse computed Fibonacci values

Solution

1. Step 1: Understand repeated calculations in recursion

   Recursive Fibonacci calls fib(n-1) and fib(n-2) repeatedly, causing many duplicate calls and inefficiency.

2. Step 2: Use memoization to store results

   Memoization saves computed Fibonacci values in a cache, so repeated calls return stored results instantly, improving speed.

3. Final Answer:

   Use memoization to store and reuse computed Fibonacci values -> Option D

4. Quick Check:

   Memoization avoids repeated work [OK]

Hint: Store results to avoid repeated recursive calls [OK]

Common Mistakes:

• Increasing recursion depth doesn't fix inefficiency
• Using loops without caching still repeats work
• Calling fib(n-1) twice wastes time