Fibonacci Using Recursion in DSA Typescript - 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 for fibonacci(n)

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

Execution Sample

DSA Typescript

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

console.log(fibonacci(4));

Calculates the 4th Fibonacci number by recursively summing previous two Fibonacci numbers.

Execution Table

Step	Call	Arguments	Return Value	Stack Depth	Action
1	fibonacci	4	?	1	Check if 4 <= 1 (No), call fibonacci(3) and fibonacci(2)
2	fibonacci	3	?	2	Check if 3 <= 1 (No), call fibonacci(2) and fibonacci(1)
3	fibonacci	2	?	3	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
4	fibonacci	1	1	4	1 <= 1 (Yes), return 1
5	fibonacci	0	0	4	0 <= 1 (Yes), return 0
6	fibonacci	2	1	3	Return fibonacci(1)+fibonacci(0) = 1+0=1
7	fibonacci	1	1	3	1 <= 1 (Yes), return 1
8	fibonacci	3	2	2	Return fibonacci(2)+fibonacci(1) = 1+1=2
9	fibonacci	2	?	2	Check if 2 <= 1 (No), call fibonacci(1) and fibonacci(0)
10	fibonacci	1	1	3	1 <= 1 (Yes), return 1
11	fibonacci	0	0	3	0 <= 1 (Yes), return 0
12	fibonacci	2	1	2	Return fibonacci(1)+fibonacci(0) = 1+0=1
13	fibonacci	4	3	1	Return fibonacci(3)+fibonacci(2) = 2+1=3
14	-	-	-	-	End of recursion, final result is 3

💡 Recursion ends when calls reach n <= 1, returning n directly.

Variable Tracker

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

Key Moments - 3 Insights

Why does fibonacci(2) get called multiple times?

Because the function calls fibonacci(n-1) and fibonacci(n-2) separately each time without storing results, as seen in steps 3, 9, and 12 in the execution_table.

Why does the recursion stop at n <= 1?

Because the base case returns n directly when n is 0 or 1, stopping further recursive calls, shown in steps 4, 5, 7, 10, and 11.

What does stack depth represent in the variable_tracker?

It shows how many recursive calls are active at once, increasing when calling deeper and decreasing when returning, as seen increasing from 1 to 4 and then back down.

Visual Quiz - 3 Questions

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

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Return Value' column at step 8 for fibonacci(3).

At which step does the recursion first reach the base case?

A Step 2

B Step 6

C Step 4

D Step 9

💡 Hint

Look for the first step where 'Return Value' is directly n because n <= 1.

If we change the input to fibonacci(5), how would the stack depth change compared to fibonacci(4)?

A Maximum stack depth would stay the same

B Maximum stack depth would increase by 1

C Maximum stack depth would decrease

D Stack depth would be zero

💡 Hint

Stack depth increases with input size as recursion goes deeper, see variable_tracker for fibonacci(4).

Concept Snapshot

function fibonacci(n: number): number {
  if (n <= 1) return n;  // base case
  return fibonacci(n - 1) + fibonacci(n - 2);  // recursive calls
}

- Recursion stops when n is 0 or 1
- Each call waits for two smaller calls
- Results sum back up to final answer

Full Transcript

This visualization shows how the recursive Fibonacci function works step-by-step. The function calls itself with smaller numbers until it reaches the base case where n is 0 or 1, then returns that value. Each call waits for the results of fibonacci(n-1) and fibonacci(n-2), adds them, and returns the sum. The execution table tracks each call, its arguments, return values, and stack depth showing how recursion grows and shrinks. The variable tracker shows how n and return values change during execution. Key moments clarify why base cases stop recursion and why some calls repeat. The quiz tests understanding of return values, base cases, and recursion depth. This helps learners see recursion as a chain of calls building up and returning 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