PPractick

The problem

The Fibonacci sequence, 0, 1, 1, 2, 3, 5, 8, ..., where each number is the sum of the two before it, is the standard first example of multiple recursion: a function that calls itself more than once. Written directly from the definition, it's beautifully short and catastrophically slow, because the same values get recomputed again and again. The exercise is to write the direct recursion, see exactly why it explodes (by counting calls), and then fix it with memoisation and with a simple loop.

Example: fib(10) = 55; fib(50) = 12586269025.

Function signature

long long fibRecursive(int n);   // direct recursion: exponential
long long fibMemo(int n);        // memoised recursion: linear
long long fibIterative(int n);   // two variables: linear time, constant space

Test cases

Input n	Output	Explanation
0	0	Base case
1	1	Base case
2	1	1 + 0
10	55
30	832040	Direct recursion makes about 2.7 million calls here
50	12586269025	Exceeds int; direct recursion would take minutes

(Confirm: fib(0) = 0, fib(1) = 1; 0 ≤ n ≤ 90 so the result fits in a long long.)

How interviewers phrase it

• "Find the Nth Fibonacci number" (LeetCode 509).
• "Why is the recursive solution slow? How would you speed it up?"
• Variants with the same structure: Climbing Stairs, tiling problems, and counting binary strings without consecutive 1s.

Clarifying questions to ask

1. Is fib(0) = 0 or 1? (Indexing conventions differ.)
2. How large can N be? (Overflow; maybe a modulo is needed.)
3. Is recursion required, or is any approach fine?

Follow-ups to expect

1. "What's the complexity of the direct recursion?"
2. "How does memoisation fix it?"
3. "Can you use O(1) space?"
4. "Can you do better than O(n)?"
5. "What's the recursion depth?"

Related questions

• Pow(x, n) Easy
• Count Good Numbers Medium
• Frog Jump Medium
• Frog jump with K distances Medium
• Different Ways to Evaluate a Boolean Expression Medium
• Understand recursion by print something N times Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in