Fibonacci Using Recursion in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in a recursive Fibonacci function?

The base case returns the first two Fibonacci numbers directly, usually when n is 0 or 1, returning n itself to stop further recursion.

beginner

Explain how recursion works in calculating Fibonacci numbers.

Recursion breaks the problem into smaller parts by calling the Fibonacci function for (n-1) and (n-2), then adds their results to get the nth Fibonacci number.

intermediate

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

The time complexity is exponential, specifically O(2^n), because it recalculates the same Fibonacci numbers multiple times.

intermediate

Why can recursion be inefficient for Fibonacci calculation without optimization?

Because it repeats calculations for the same inputs many times, leading to a large number of function calls and slow performance.

beginner

Show the TypeScript function signature for a recursive Fibonacci function.

function fibonacci(n: number): number

What does the recursive Fibonacci function return when n is 0?

A 0

B 1

C n

D -1

The base case for n=0 returns 0 as the first Fibonacci number.

Which two previous Fibonacci numbers does the recursive function add to get the nth number?

A n and n-1

B n-1 and n-2

C n-2 and n-3

D n-3 and n-4

The function calls fibonacci(n-1) and fibonacci(n-2) and adds their results.

What is a major drawback of the naive recursive Fibonacci approach?

A Does not work for n=0

B Uses too much memory

C Exponential time complexity

D Returns wrong results

The naive recursion has exponential time complexity due to repeated calculations.

Which technique can improve recursive Fibonacci efficiency?

A Memoization

B Sorting

C Loop unrolling

D Binary search

Memoization stores results of previous calls to avoid repeated work.

What is the output of fibonacci(3) using recursion?

A 1

B 3

C 5

D 2

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

Describe how a recursive function calculates the nth Fibonacci number.

Think about how the function calls itself with smaller inputs.

Explain why naive recursion for Fibonacci is inefficient and how to improve it.

Consider what happens when the function calls overlap.