Fibonacci Using Recursion in DSA Java - 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 sums results on return.

Execution Sample

DSA Java

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

System.out.println(fibonacci(4));

Calculates the 4th Fibonacci number by recursive calls.

Execution Table

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

💡 All recursive calls resolved, final Fibonacci number for n=4 is 3

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	Final
n	4	1 (in fibonacci(1))	2 (in fibonacci(2))	3 (in fibonacci(3))	2 (in fibonacci(2))	4 (initial call)
Return Value	-	1	1	2	1	3

Key Moments - 3 Insights

Why does fibonacci(4) call fibonacci(3) and fibonacci(2) instead of calculating directly?

Because the function uses recursion to break the problem into smaller parts, as shown in steps 1 and 2 of the execution_table.

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

This is the base case stopping recursion, returning 0 or 1 directly as shown in steps 4 and 5.

How does the function combine results from fibonacci(n-1) and fibonacci(n-2)?

After both recursive calls return, their results are added and returned, as seen 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 1

B 2

C 3

D 0

💡 Hint

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

At which step does the recursion reach the base case for fibonacci(0)?

A Step 5

B Step 4

C Step 10

D Step 11

💡 Hint

Look for the step where fibonacci(0) returns a value in the execution_table.

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

A 3

B 7

C 5

D 9

💡 Hint

Count calls for fibonacci(4) in execution_table and compare to fibonacci(3) calls.

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
- Results sum on return
- Simple but inefficient for large n

Full Transcript

This visualization shows how the Fibonacci function uses recursion. The function calls itself with smaller numbers until it reaches the base case where n is 0 or 1. At that point, it returns the value directly. Then, the function adds the results of the two smaller calls as it returns back up the call stack. The execution table tracks each call, the condition check, and the return values. The variable tracker shows how n and return values change during execution. Key moments clarify why recursion splits the problem and how base cases stop it. The quiz tests understanding of return values and call counts. This method is clear but can be slow for large inputs due to repeated calls.

Practice

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

easy

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

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

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

D. Each number is the square of the previous number

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 B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds two previous numbers to get next [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 Java?

easy

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

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

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

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

Solution

1. Step 1: Identify correct base case condition

   The base case must check if n is 0 or 1 using '==' for comparison and logical OR '||'.

2. Step 2: Check syntax correctness

   if (n == 0 || n == 1) return n; uses correct comparison operators and logical OR. Others use incorrect operators or logic.

3. Final Answer:

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

4. Quick Check:

   Base case uses '==' and '||' [OK]

Hint: Use '==' for comparison and '||' for OR in base case [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Using '&&' instead of '||' in base case
• Incorrect negation or logic in condition

3. What is the output of the following Java code?

public class FibTest {
  public static int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 7

B. 5

C. 4

D. 3

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 main method prints fib(4), which is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Calculate fib(n) by adding fib(n-1) and fib(n-2) [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Miscomputing base cases
• Adding wrong recursive results

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

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

medium

A. Change 'return 0;' to 'return n;' in base case

B. Change 'if' condition to 'n == 2 || n == 3'

C. Add a loop inside the function

D. Remove the base case entirely

Solution

1. Step 1: Analyze base case return value

   The base case returns 0 for both n=0 and n=1, but fib(1) should return 1.

2. Step 2: Correct base case return

   Return n for base cases 0 and 1 to correctly represent Fibonacci values.

3. Final Answer:

   Change 'return 0;' to 'return n;' in base case -> Option A

4. Quick Check:

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

Hint: Base case must return n, not always 0 [OK]

Common Mistakes:

• Returning 0 for fib(1)
• Changing base case condition incorrectly
• Removing base case causing infinite recursion

5. You want to find the 6th Fibonacci number using recursion but want to avoid repeated calculations. Which technique can you apply to optimize the recursive Fibonacci function?

hard

A. Increase the base case to n == 5

B. Replace recursion with an infinite loop

C. Use memoization to store and reuse computed results

D. Use a global variable to count calls

Solution

1. Step 1: Understand recursion inefficiency

   Recursive Fibonacci recalculates the same values many times, causing slow performance.

2. Step 2: Apply memoization

   Memoization stores results of fib(n) in a cache so repeated calls return cached values, improving speed.

3. Final Answer:

   Use memoization to store and reuse computed results -> Option C

4. Quick Check:

   Memoization avoids repeated calculations [OK]

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

Common Mistakes:

• Changing base case incorrectly
• Using infinite loops causing crashes
• Counting calls without optimization