Fibonacci Using Recursion in DSA Javascript

Mental Model

Calculate each Fibonacci number by adding the two before it, using a function that calls itself.

Analogy: Like climbing stairs where to reach step n, you first need to know how to reach steps n-1 and n-2.

fib(4)
  /    \
fib(3)  fib(2)
 /  \     /  \
fib(2) fib(1) fib(1) fib(0)
 /  \
fib(1) fib(0)

Dry Run Walkthrough

Input: Calculate fib(4)

Goal: Find the 4th Fibonacci number using recursion

Step 1: Call fib(4), which calls fib(3) and fib(2)

fib(4) -> fib(3) + fib(2)

Why: To find fib(4), we need fib(3) and fib(2)

Step 2: Call fib(3), which calls fib(2) and fib(1)

fib(3) -> fib(2) + fib(1)

Why: To find fib(3), we need fib(2) and fib(1)

Step 3: Call fib(2), which calls fib(1) and fib(0)

fib(2) -> fib(1) + fib(0)

Why: To find fib(2), we need fib(1) and fib(0)

Step 4: fib(1) returns 1 and fib(0) returns 0, so fib(2) = 1 + 0 = 1

fib(2) = 1

Why: Base cases return fixed values

Step 5: fib(1) returns 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2

fib(3) = 2

Why: Combine results to get fib(3)

Step 6: fib(2) already calculated as 1, so fib(4) = fib(3) + fib(2) = 2 + 1 = 3

fib(4) = 3

Why: Final result combines previous two Fibonacci numbers

Result:

fib(4) = 3

Annotated Code

DSA Javascript

class Fibonacci {
  static fib(n) {
    if (n === 0) return 0; // base case: fib(0) = 0
    if (n === 1) return 1; // base case: fib(1) = 1
    return Fibonacci.fib(n - 1) + Fibonacci.fib(n - 2); // recursive call
  }
}

// Driver code
const n = 4;
console.log(`fib(${n}) = ${Fibonacci.fib(n)}`);

if (n === 0) return 0; // base case: fib(0) = 0

return 0 when n is 0 to stop recursion

if (n === 1) return 1; // base case: fib(1) = 1

return 1 when n is 1 to stop recursion

return Fibonacci.fib(n - 1) + Fibonacci.fib(n - 2); // recursive call

calculate fib(n) by adding fib(n-1) and fib(n-2)

Output

fib(4) = 3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, doubling work

Space: O(n) due to the maximum depth of the recursion call stack

vs Alternative: Iterative approach is O(n) time and O(1) space, much more efficient

Edge Cases

n = 0

Returns 0 immediately using base case

DSA Javascript

if (n === 0) return 0; // base case: fib(0) = 0

n = 1

Returns 1 immediately using base case

DSA Javascript

if (n === 1) return 1; // base case: fib(1) = 1

negative n

No guard in code, will cause infinite recursion or error

DSA Javascript

No explicit guard for negative input

When to Use This Pattern

When you see a problem asking for a sequence where each value depends on previous two, try recursion with base cases to break it down.

Common Mistakes

Mistake: Forgetting base cases causing infinite recursion
Fix: Add conditions to return fixed values for fib(0) and fib(1)

Mistake: Calling fib(n-1) and fib(n-2) without returning their sum
Fix: Return the sum of fib(n-1) and fib(n-2) to get correct result

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to find Fibonacci numbers recursively.

The key is to stop recursion at base cases fib(0) and fib(1) and build up from there.

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