Fibonacci Using Recursion in DSA C# - Execution Trace

Concept Flow - Fibonacci Using Recursion

Call fibonacci(n)

↓

Check if 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 base cases, then returns and sums results back up.

Execution Sample

DSA C#

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

Calculates the nth Fibonacci number by calling itself with n-1 and n-2 until base cases.

Execution Table

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

💡 All recursive calls completed and returned the Fibonacci number for n=4

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 13	Final
n	4	1 (in fibonacci(1))	2 (in fibonacci(2))	3 (in fibonacci(3))	4 (in fibonacci(4))	3 (final result)
Return Value		1	1	2	3	3
Stack Depth	1	4	3	2	1	0

Key Moments - 3 Insights

Why do we see multiple calls to fibonacci with the same n value?

Because fibonacci(n-1) and fibonacci(n-2) are called separately each time, causing repeated calls for the same n, as shown in steps 3 and 9 both calling fibonacci(2).

Why does the recursion stop at n <= 1?

Because n <= 1 is the base case that returns a value directly without further calls, stopping infinite recursion. This is seen in steps 4, 5, 7, 10, and 11.

How does the function combine results from recursive calls?

After both fibonacci(n-1) and fibonacci(n-2) return, their results are added and returned as the result for fibonacci(n), as in steps 6, 8, 12, and 13.

Visual Quiz - 3 Questions

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

A 2

B 3

C 1

D 0

💡 Hint

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

At which step does the recursion first reach the base case for n=1?

A Step 2

B Step 4

C Step 6

D Step 10

💡 Hint

Look for the first step where 'Base case n<=1' is mentioned in the Action column.

If we call fibonacci(5) instead of fibonacci(4), how would the stack depth change at the first call?

A It would decrease by 1

B It would stay the same

C It would increase by 1

D It would double

💡 Hint

Compare the Stack Depth column at step 1 for fibonacci(4) and imagine one more recursive call.

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 combine as calls return
- Simple but has repeated calls causing inefficiency

Full Transcript

This visualization shows how the Fibonacci function calls itself recursively. Starting with fibonacci(4), it checks if n is less than or equal to 1. If yes, it returns n immediately. Otherwise, it calls fibonacci(n-1) and fibonacci(n-2). These calls continue until base cases are reached at n=1 or n=0. Then, the function returns values back up the call stack, adding results from the two recursive calls. The execution table tracks each call, the current n, actions taken, return values, and stack depth. The variable tracker shows how n, return values, and stack depth change over time. Key moments clarify why repeated calls happen, why base cases stop recursion, and how results combine. The quiz tests understanding of return values, base case steps, and stack depth changes. The snapshot summarizes the recursive Fibonacci logic and behavior.

Practice

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

easy

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

B. Each number is the sum 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: Apply to recursion context

   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 B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Remember Fibonacci adds two previous numbers [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 C# syntax to define a recursive Fibonacci function header?

easy

A. void Fibonacci(int n)

B. int Fibonacci()

C. int Fibonacci(int n)

D. int Fibonacci(int)

Solution

1. Step 1: Identify function return type and parameters

   The Fibonacci function returns an integer and takes an integer parameter for the position.

2. Step 2: Match correct C# syntax

   Correct syntax includes return type, function name, and parameter with type: int Fibonacci(int n)

3. Final Answer:

   int Fibonacci(int n) -> Option C

4. Quick Check:

   Function returns int and takes int parameter [OK]

Hint: Function must return int and take int parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing parameter type or name
• Incorrect parameter list syntax

3. What is the output of this C# code snippet?

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

Console.WriteLine(Fibonacci(4));

medium

A. 3

B. 5

C. 4

D. 7

Solution

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

   Fibonacci(4) = Fibonacci(3) + Fibonacci(2). Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 1 + 1 = 2. Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = 1 + 0 = 1. So Fibonacci(4) = 2 + 1 = 3.

2. Step 2: Confirm output

   The printed output is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Trace calls down to base cases to sum results [OK]

Common Mistakes:

• Confusing Fibonacci(4) with Fibonacci(5)
• Miscounting base cases
• Adding wrong recursive results

4. Identify the error in this recursive Fibonacci function:

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

medium

A. The recursive call uses subtraction instead of addition

B. Parameter type is missing

C. Function lacks return type

D. Base cases are incorrect

Solution

1. Step 1: Check base cases

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

2. Step 2: Analyze recursive return statement

   The function uses subtraction (Fibonacci(n - 1) - Fibonacci(n - 2)) instead of addition, which is incorrect for Fibonacci sequence.

3. Final Answer:

   The recursive call uses subtraction instead of addition -> Option A

4. Quick Check:

   Fibonacci sums previous two, not subtracts [OK]

Hint: Fibonacci adds two previous calls, not subtracts [OK]

Common Mistakes:

• Using subtraction instead of addition in recursion
• Forgetting to return in base cases
• Missing parameter or return type in function

5. How can you optimize the recursive Fibonacci function to avoid repeated calculations?

hard

A. Increase the recursion depth limit

B. Replace recursion with a while loop only

C. Use subtraction instead of addition in recursion

D. Use memoization to store and reuse computed values

Solution

1. Step 1: Understand problem with naive recursion

   Naive recursion recalculates Fibonacci values many times, causing inefficiency.

2. Step 2: Apply memoization technique

   Memoization stores results of Fibonacci calls in a cache to reuse, avoiding repeated work.

3. Final Answer:

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

4. Quick Check:

   Memoization optimizes recursion by caching results [OK]

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

Common Mistakes:

• Thinking only loops can optimize recursion
• Increasing recursion depth does not improve efficiency
• Using subtraction breaks Fibonacci logic