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

↓

Return sum

The function calls itself with smaller numbers until it reaches 0 or 1, then adds results back up.

Execution Sample

DSA Javascript

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(4));

Calculates the 4th Fibonacci number by calling itself recursively.

Execution Table

Step	Call	Arguments	Return Value	Stack Depth
1	fibonacci	4	?	1
2	fibonacci	3	?	2
3	fibonacci	2	?	3
4	fibonacci	1	1	4
5	fibonacci	0	0	4
6	fibonacci	2 returns	1	3
7	fibonacci	1	1	3
8	fibonacci	3 returns	2	2
9	fibonacci	2	?	2
10	fibonacci	1	1	3
11	fibonacci	0	0	3
12	fibonacci	2 returns	1	2
13	fibonacci	4 returns	3	1

💡 All recursive calls reached base case (n <= 1), then returned values summed up to final result.

Variable Tracker

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

Key Moments - 3 Insights

Why does fibonacci(4) call fibonacci(3) and fibonacci(2) before returning?

Because the function adds fibonacci(n-1) and fibonacci(n-2) to get fibonacci(n). See steps 2 and 3 in execution_table.

Why do calls with n=1 or n=0 return immediately?

These are base cases that stop recursion. At steps 4 and 5, the function returns 1 and 0 directly.

How does the function combine results from smaller calls?

After base cases return, the function adds their results as shown in steps 6, 8, and 13.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of fibonacci(2) at step 6?

A 2

B 1

C 3

D 0

💡 Hint

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

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

A Step 5

B Step 10

C Step 4

D Step 11

💡 Hint

Look for the call with argument 0 and return value 0 in execution_table.

If fibonacci(5) was called instead, how would the stack depth change at the first call?

A It would increase to 4

B It would increase to 3

C It would increase to 5

D It would increase to 2

💡 Hint

Stack depth grows with each recursive call; fibonacci(4) starts at 1, so fibonacci(5) adds one more call.

Concept Snapshot

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

- Calls itself with smaller n
- Stops at n=0 or 1 (base cases)
- Adds results to get fibonacci(n)

Full Transcript

The fibonacci function uses recursion by calling itself with smaller numbers until it reaches 0 or 1, which are base cases. Each call waits for the results of fibonacci(n-1) and fibonacci(n-2), then adds them to find the result for fibonacci(n). The execution table shows each call, its arguments, return values, and stack depth. Base cases return immediately, stopping further calls. The stack depth increases with each recursive call and decreases as calls return. This process continues until the original call returns the final Fibonacci number.

Practice

1. What does a recursive Fibonacci function do when called with fib(4)?

easy

A. Throws a syntax error because recursion is not allowed

B. Returns 4 immediately without any calculation

C. Runs an infinite loop without returning

D. Calculates the 4th Fibonacci number by calling itself with smaller numbers

Solution

1. Step 1: Understand recursive calls for fib(4)

   The function calls fib(3) and fib(2) to calculate fib(4).

2. Step 2: Combine results of smaller calls

   fib(3) and fib(2) are calculated recursively and their sum is returned as fib(4).

3. Final Answer:

   Calculates the 4th Fibonacci number by calling itself with smaller numbers -> Option D

4. Quick Check:

   Recursive calls break problem into smaller parts [OK]

Hint: Recursion breaks problem into smaller calls [OK]

Common Mistakes:

• Thinking recursion returns input directly
• Assuming recursion causes infinite loop always
• Confusing recursion with iteration

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

easy

A. if (n = 0) return 0;

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

C. if n == 1 then return 1

D. if (n > 1) return n;

Solution

1. Step 1: Identify correct JavaScript syntax for base case

   The base case must check if n is 0 or 1 and return n using proper JavaScript syntax.

2. Step 2: Validate each option

   if (n <= 1) return n; uses correct syntax: if (n <= 1) return n; Options A and B have syntax errors or wrong operators, D is logically incorrect.

3. Final Answer:

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

4. Quick Check:

   Base case uses if (n <= 1) return n; [OK]

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

Common Mistakes:

• Using assignment (=) instead of comparison (== or ===)
• Missing parentheses in if condition
• Incorrect logical condition for base case

3. What is the output of the following code?

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(5));

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Trace fib(5) recursive calls

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

2. Step 2: Calculate values bottom-up

   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:

   Fibonacci(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Miscounting recursive calls
• Assuming fib(5) is 8 or 13 incorrectly

4. Identify the error in this recursive Fibonacci function:

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

medium

A. The recursive step uses subtraction instead of addition

B. The base cases are incorrect

C. The function will cause infinite recursion

D. The function syntax is invalid

Solution

1. Step 1: Check base cases correctness

   Base cases for n==0 and n==1 correctly return 0 and 1 respectively.

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 A

4. Quick Check:

   Fibonacci sums previous two, not subtracts [OK]

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

Common Mistakes:

• Using wrong operator (+ vs -)
• Confusing base cases
• Assuming syntax error when logic is wrong

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

hard

A. Remove base cases to speed up recursion

B. Increase the recursion depth limit

C. Use memoization to store and reuse computed values

D. Replace recursion with a while loop only

Solution

1. Step 1: Understand repeated calculations in recursion

   Recursive Fibonacci recalculates same values many times, causing inefficiency.

2. Step 2: Apply memoization to store results

   Memoization saves results of fib(n) calls in a cache to reuse and avoid repeated work.

3. Final Answer:

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

4. Quick Check:

   Memoization improves recursion efficiency [OK]

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

Common Mistakes:

• Thinking increasing recursion limit helps
• Believing loops are only solution
• Removing base cases causing infinite recursion