Fibonacci Using Recursion in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Recursive Call

What is the output of the following TypeScript code that calculates Fibonacci numbers recursively?

DSA Typescript

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

console.log(fibonacci(5));

A 5

B 3

C 13

D 8

💡 Hint

Remember the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8...

The fibonacci function returns the nth Fibonacci number. fibonacci(5) returns 5 because the sequence is 0,1,1,2,3,5,8 and fib(5) = 5.

❓ Predict Output

intermediate

Value of Variable After Recursive Fibonacci

What is the value of variable `result` after running this code?

DSA Typescript

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

A 2

B 5

C 3

D 1

💡 Hint

Calculate fibonacci(3) step by step.

fibonacci(3) = fibonacci(2) + fibonacci(1) = (fibonacci(1) + fibonacci(0)) + 1 = (1 + 0) + 1 = 1 + 1 = 2.

🔧 Debug

advanced

Identify the Error in Fibonacci Recursive Function

What error will this TypeScript code produce when run?

DSA Typescript

function fibonacci(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 3);
}
console.log(fibonacci(4));

A Output is 3

B Output is 5

C TypeError: fibonacci is not a function

D Stack overflow error due to infinite recursion

💡 Hint

Check the recursive calls carefully for base cases.

The function calls fibonacci(n - 3) without proper base case coverage for n < 3, causing infinite recursion and stack overflow.

🧠 Conceptual

advanced

Time Complexity of Recursive Fibonacci

What is the time complexity of the naive recursive Fibonacci function?

DSA Typescript

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

A O(n^2)

B O(2^n)

C O(n)

D O(log n)

💡 Hint

Consider how many calls are made for each fibonacci call.

Each call to fibonacci(n) makes two calls to fibonacci(n-1) and fibonacci(n-2), leading to exponential growth in calls, so time complexity is O(2^n).

🚀 Application

expert

Output of Memoized Fibonacci Recursive Function

What is the output of this memoized Fibonacci function when called with fibonacci(6)?

DSA Typescript

function fibonacci(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
console.log(fibonacci(6));

A 21

B 34

C 8

D 13

💡 Hint

Memoization avoids repeated calculations, but the Fibonacci sequence values remain the same.

fibonacci(6) returns 8 because the sequence is 0,1,1,2,3,5,8,13 and the 6th index (0-based) is 8.