Overview
Fibonacci recursion se — elegant hai lekin slow! fib(n) = fib(n-1) + fib(n-2), yaar ye O(2^n) hai.
Analogy
Jaise family tree mein pata karo — papaji ke papaji ke... — har kisi se seedha puchho lekin sab repeat karte hain.
Step-by-step
- Base case: fib(0) = 0, fib(1) = 1
- Recursive: fib(n) = fib(n-1) + fib(n-2)
- Simple lekin slow — fib(50) practically hang ho jaata hai
- Memoize karo speed ke liye
Visual
fib(5)
+-- fib(4)
| +-- fib(3)
| | +-- fib(2)...
| +-- fib(2) <- DUPLICATE!
+-- fib(3) <- DUPLICATE!
Common mistakes
- Memoization ke bina large n — exponential time
- fib(0) = 0 ya 1? Convention important
- Stack overflow for large n
Practice questions
- @functools.lru_cache se memoized recursive Fibonacci banao
- Call tree draw karo fib(5) ke liye — duplicates dekho