Recursion — Animate | AI Wisdom

← Back to topic
🎞 ANIMATE · Mode 3 of 5 · +100 XP— Recursion (Fibonacci)
📞Call
🏁Base
⬆️Return
💾Memo
🎯 Next: Test →
Step 1 / 4
Speed
Initial call
fibNaive(4) — starts the recursive call tree💡 Analogy
Like asking "what is 4?" by asking two friends who each ask two more friends.
To compute fib(4), we need fib(3) + fib(2). Each of those needs more calls.
Console Output
> fibNaive(4)
>   fibNaive(3)
>     fibNaive(2)
>       ...
●recursion.ts
Initial callL2–4
1// Naive recursive Fibonacci (shows call stack growth)
2function fibNaive(n: number): number {
3  if (n <= 1) return n;           // Base case
4  return fibNaive(n - 1) + fibNaive(n - 2);
5}
6 
7// Memoised Fibonacci (O(n) time)
8function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
9  if (n <= 1) return n;
10  if (memo.has(n)) return memo.get(n)!;  // Cache hit
11  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
12  memo.set(n, result);
13  return result;
14}
15 
16fibNaive(5); // → 5  (calls: 15)
17fibMemo(5);  // → 5  (calls: 9, then cached)
17 lines
Timeline — 4 Steps
Initial call
fibNaive(4) — starts the recursive call tree💡 Analogy
Like asking "what is 4?" by asking two friends who each ask two more friends.
To compute fib(4), we need fib(3) + fib(2). Each of those needs more calls.
Console Output
> fibNaive(4)
>   fibNaive(3)
>     fibNaive(2)
>       ...

fibNaive(4) — starts the recursive call tree

fibNaive(4) — starts the recursive call tree

Was this page helpful?

Discussion

fibNaive(4) — starts the recursive call tree

fibNaive(4) — starts the recursive call tree

Was this page helpful?

Discussion