Fibonacci Using Recursion in DSA Typescript

Mental Model

Fibonacci numbers are found by adding the two numbers before it, starting from 0 and 1. Recursion means the function calls itself to find these numbers step by step.

Analogy: Imagine climbing stairs where each step depends on the sum of the two previous steps you took. To know how high you are on step n, you look back at steps n-1 and n-2 and add them.

fib(4)
  ↑
fib(3) + fib(2)
 ↑       ↑
fib(2)+fib(1) fib(1)+fib(0)
 ↑   ↑     ↑    ↑
1   1     1    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 the two previous Fibonacci numbers

Step 2: fib(3) calls fib(2) and fib(1)

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

Why: fib(3) breaks down further to find its two previous numbers

Step 3: fib(2) calls fib(1) and fib(0), both base cases return 1 and 0

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

Why: Base cases stop recursion and provide known values

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

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

Why: Calculate fib(3) and fib(2) values to sum for fib(4)

Step 5: Sum all: fib(4) = (1 + 1) + 1 = 3

fib(4) = 3

Why: Final addition gives the 4th Fibonacci number

Result:

fib(4) = 3

Annotated Code

DSA Typescript

class Fibonacci {
  static fib(n: number): number {
    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

stop recursion when n is 0 and return 0

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

stop recursion when n is 1 and return 1

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

call fib for previous two numbers and add results

Output

fib(4) = 3

Complexity Analysis

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

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

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

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Typescript

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

n = 1

Returns 1 immediately as base case

DSA Typescript

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

n is negative

No guard in code; recursion will continue indefinitely (stack overflow)

DSA Typescript

No guard for negative input in code

When to Use This Pattern

When you see a problem asking for a sequence where each value depends on previous ones, try recursion to break it down into smaller subproblems.

Common Mistakes

Mistake: Missing base cases causing infinite recursion
Fix: Add base cases for n=0 and n=1 to stop recursion

Mistake: Calling fib(n-1) and fib(n-2) without return causing undefined results
Fix: Return the sum of fib(n-1) and fib(n-2) properly

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs until base cases.

Use when you want a simple, clear way to find Fibonacci numbers and understand recursion.

The key is breaking the problem into two smaller Fibonacci calls and combining their results.

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 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: Recognize recursion use

   Recursion calls the function itself to calculate previous two numbers and sums them.

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 last two numbers, not multiply or subtract [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or squares with addition
• Assuming Fibonacci is a product sequence

2. Which of the following is the correct TypeScript function signature for a recursive Fibonacci function?

easy

A. function fib(n: string): string

B. function fib(n: boolean): boolean

C. function fib(n: number): number

D. function fib(): void

Solution

1. Step 1: Identify input and output types

   The Fibonacci function takes a number input and returns a number output.

2. Step 2: Match correct function signature

   Only the signature with number input and number output matches the Fibonacci function requirements.

3. Final Answer:

   function fib(n: number): number -> Option C

4. Quick Check:

   Input and output types must be number [OK]

Hint: Fibonacci input/output are numbers, not strings or booleans [OK]

Common Mistakes:

• Using wrong parameter types like string or boolean
• Missing return type or using void
• Confusing function signature syntax

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

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

medium

A. 5

B. 7

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

   The console.log prints 5 as the result of fib(4).

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(4) = 5 [OK]

Hint: Trace fib calls step-by-step to sum previous two results [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Miscounting base cases fib(0) and fib(1)
• Adding wrong recursive results

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

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

medium

A. Change base case n == 0 to n <= 0

B. Change subtraction to addition in return statement

C. Remove base cases completely

D. Change function to return string instead of number

Solution

1. Step 1: Analyze return statement

   The function uses subtraction (fib(n - 1) - fib(n - 2)) which is incorrect for Fibonacci.

2. Step 2: Correct the operation

   Fibonacci requires addition of previous two numbers, so change '-' to '+'.

3. Final Answer:

   Change subtraction to addition in return statement -> Option B

4. Quick Check:

   Fibonacci sums previous two numbers [OK]

Hint: Fibonacci adds, never subtracts previous two results [OK]

Common Mistakes:

• Using subtraction instead of addition
• Removing base cases causing infinite recursion
• Changing return type unnecessarily

5. Given the recursive Fibonacci function below, what is the output of fib(0) and fib(1)? Why are these base cases important?

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

hard

A. fib(0) = 0, fib(1) = 1; base cases are optional

B. fib(0) = 1, fib(1) = 0; base cases speed up recursion

C. fib(0) = 1, fib(1) = 1; base cases prevent wrong output

D. fib(0) = 0, fib(1) = 1; base cases stop infinite recursion

Solution

1. Step 1: Evaluate base cases fib(0) and fib(1)

   fib(0) returns 0 and fib(1) returns 1 as per the condition n <= 1 returns n.

2. Step 2: Understand importance of base cases

   Base cases stop the recursion from continuing infinitely by providing direct answers for smallest inputs.

3. Final Answer:

   fib(0) = 0, fib(1) = 1; base cases stop infinite recursion -> Option D

4. Quick Check:

   Base cases return 0 and 1 to end recursion [OK]

Hint: Base cases return n for n ≤ 1 to stop recursion [OK]

Common Mistakes:

• Mixing up fib(0) and fib(1) values
• Thinking base cases are optional
• Ignoring recursion stopping condition