Overview
Recursive Fibonacci: f(n)=f(n-1)+f(n-2). Simple lekin exponential time, memoization chahiye.
Analogy
Jaise family tree—har insaan parents se information leta hai.
Step-by-step
- Base cases: f(0)=0, f(1)=1
- Warna: return f(n-1)+f(n-2)
- Yeh O(2^n) hai—bahut slow
- @lru_cache se O(n) mein improve karo
Visual
fib(4)
├─fib(3) fib(2)
│ ├─fib(2) fib(1) ├─fib(1) fib(0)
Common mistakes
- Bade n ke liye memoization ke bina use karna
- Base cases 0 ya negative numbers galat handle karna
Practice questions
- fib() ko @functools.lru_cache se decorate karo
- Bina memoization/memoization ke saath/iterative ka time compare karo
Time
O(2^n) bina memoization, O(n) saath mein