Problem link ও উৎস
- **Original source:** Classic recursion exercise
- **Platform:** LeetCode —
- **Topic:** recursion (decrease-and-conquer → memoization)
- **Difficulty:** Easy
- **Pattern:** decrease-and-conquer, দুটো recursive call → recursion tree
- **Basic idea inherited from:** loops; recursion tree-র ছবি
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `n` দেওয়া আছে। Fibonacci sequence-টা শুরু হয় `0, 1` দিয়ে, তারপর প্রতিটা সংখ্যা তার আগের দুটোর যোগফল: `0, 1, 1, 2, 3, 5, 8, 13, ...`। তোমার কাজ: `n`-তম Fibonacci সংখ্যাটা বের করা, যেখানে `F(0) = 0` আর `F(1) = 1`।
```text
index : 0 1 2 3 4 5 6 7
value : 0 1 1 2 3 5 8 13
```
### Input ও output {#8-example-input-and-output}
```text
Input : n = 2 -> Output: 1 (1 + 0)
Input : n = 4 -> Output: 3 (2 + 1)
Input : n = 10 -> Output: 55
Edge case 1 (সবচেয়ে ছোট): n = 0 -> Output: 0
Edge case 2 (দ্বিতীয় base): n = 1 -> Output: 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পারিবারিক গাছ ভাবো যেখানে প্রতিটা সংখ্যার "জন্ম" তার ঠিক আগের দুই পূর্বপুরুষ থেকে। তুমি যদি প্রতিবার পুরো বংশতালিকা নতুন করে গুনে দেখো, একই পূর্বপুরুষকে বহুবার গুনবে। কিন্তু একটা নোটবুকে (cache) প্রতিজনের নাম একবার লিখে রাখলে, পরেরবার শুধু খুলে দেখলেই হয় — দুবার গোনা লাগে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি হলো **loops** আর **recursion tree-র ছবি**। একটা loop দিয়ে তুমি দুটো আগের value ধরে রেখে সামনে এগোতে পারো — কিন্তু সংজ্ঞাটা নিজেই recursive (`F(n) = F(n-1) + F(n-2)`), তাই এটা recursion শেখার একদম প্রথম problem। এখানে function একবার নয়, **দুবার** নিজেকে call করে, তাই call-গুলো একটা লাইন না হয়ে একটা **tree** বানায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **recurrence relation**: `F(n) = F(n-1) + F(n-2)`, দুটো base case `F(0) = 0` আর `F(1) = 1` সহ। এটাই হলো সেই self-similar কাঠামো — বড় উত্তরটা ছোট দুটো উত্তরের যোগফল। সাথে একটা গুরুত্বপূর্ণ observation: naive recursion-এ একই subproblem **বারবার** compute হয়, যেটা memoization-এর জন্ম দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
Naive version-এ কোনো extra data structure লাগে না — শুধু **call stack**। Optimized version-এ একটা **dict (hash map)** লাগে cache হিসেবে, যাতে compute করা প্রতিটা `F(k)` মনে রাখা যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Cache-টা একটা dict কারণ আমরা argument `n` দিয়ে key করে O(1)-তে আগের উত্তর তুলে আনতে চাই। এটাই [../../05-hashing/](../../05-hashing/README.md)-এর hash-map lookup pattern — `n` → `F(n)`। এই O(1) lookup-টাই exponential কাজকে linear-এ নামিয়ে আনে, কারণ প্রতিটা আলাদা subproblem তখন ঠিক একবার solve হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সংজ্ঞাটা হুবহু code-এ নামিয়ে দাও — base case দুটো, তারপর দুটো recursive call যোগ করো।
```text
fib(n):
n <= 1 হলে n ফেরত দাও
নাহলে fib(n-1) + fib(n-2) ফেরত দাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই naive version **O(2^n)** — কারণ tree-তে মোটামুটি 2^n node, আর একই subproblem বারবার নতুন করে compute হয়। `fib(2)` দুবার, `fib(1)` তিনবার... `n` বড় হলে এই অপচয় বিস্ফোরিত হয়: `fib(30)`-এ ~2.7 million call। একই কাজ বারবার করাটাই মূল রোগ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা `F(k)`-এর উত্তর শুধু `k`-এর উপর নির্ভর করে** — pure function। তাই একবার `F(k)` বের করলে সেটা ধরে রাখলে আর কখনো নতুন করে compute করতে হয় না। Tree-র repeated node-গুলোকে এক-একটা cached value-তে collapse করে দেওয়া যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা cache (dict) রাখো। `fib(n)`-এ ঢোকার সাথে সাথে check করো cache-এ আছে কি না; থাকলে সাথে সাথে return। নাহলে compute করো, cache-এ রাখো, তারপর return। এতে প্রতিটা আলাদা subproblem ঠিক একবার compute হয় — exponential থেকে **O(n)**-এ নেমে আসে। এটাই top-down DP, আর এটাকে উল্টে একটা loop-এ table ভরলে তুমি পৌঁছে যাও [../../12-dynamic-programming/](../../12-dynamic-programming/README.md)-এ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কীভাবে দ্রুত করব?" ভাবার বদলে জিজ্ঞেস করো "একই subproblem কি দুবার compute হচ্ছে?" হ্যাঁ হলে — শুধু উত্তরটা মনে রাখো। এক লাইনের cache check পুরো exponential tree-টাকে একটা linear chain-এ বদলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
দুটো recursive call হওয়ায় call-গুলো tree বানায়। `fib(4)`-এর tree:
```text
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
লক্ষ করো: fib(2) দুবার, fib(1) তিনবার compute হচ্ছে — repeated subproblem।
memoization: প্রথমবার compute করে cache-এ রাখো, পরেরবার শুধু তুলে আনো।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Memoized `fib(5)`:
1. `fib(5)` চায় `fib(4)` ও `fib(3)`।
2. `fib(4)` চায় `fib(3)` ও `fib(2)`; `fib(3)` চায় `fib(2)` ও `fib(1)`।
3. সবচেয়ে গভীরে: `fib(1) = 1`, `fib(0) = 0` — base case, cache-এ যায়।
4. ফিরতি পথে: `fib(2) = 1` (cache), `fib(3) = 2` (cache), `fib(4) = 3` (cache)।
5. `fib(5) = fib(4) + fib(3) = 3 + 2 = 5`। প্রতিটা `fib(k)` ঠিক একবার compute হলো।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from functools import lru_cache
def fib_naive(n):
if n <= 1: # base case: F(0)=0, F(1)=1
return n
return fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: # একই logic, কিন্তু cache সহ
return n
return fib(n - 1) + fib(n - 2)
def fib_memo(n, cache=None): # manual cache (জাদুটা দেখার জন্য)
if cache is None:
cache = {}
if n in cache:
return cache[n]
if n <= 1:
return n
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
# ---- tests ----
assert fib_naive(0) == 0 # base case
assert fib_naive(1) == 1 # base case
assert fib_naive(2) == 1
assert fib_naive(10) == 55
assert fib(20) == 6765 # cached version
assert fib(30) == 832040
assert fib_memo(40) == 102334155 # manual cache, বড় n-ও দ্রুত
assert [fib(i) for i in range(8)] == [0, 1, 1, 2, 3, 5, 8, 13]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if n <= 1: return n` — দুটো base case একসাথে: `F(0)=0`, `F(1)=1`। `<=` ব্যবহার করায় কোনো base টপকে যাওয়ার ভয় নেই।
- `return fib(n-1) + fib(n-2)` — recurrence relation হুবহু; দুটো ছোট problem-কে বিশ্বাস করো (leap of faith)।
- `@lru_cache(maxsize=None)` — Python-এর built-in memoization; argument দিয়ে key করে উত্তর মনে রাখে।
- `if n in cache: return cache[n]` — manual version-এ এই লাইনটাই exponential-কে linear করে।
- `cache[n] = ...` — compute করার পর store করো, যাতে পরের বার শুধু তুলে আনা যায়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`fib_naive(10)` সংজ্ঞা মেনে `55` দেয়। `fib(20)` cache-এর সাহায্যে দ্রুত `6765` দেয়, `fib(30)` দেয় `832040`। `fib_memo(40)` manual cache দিয়ে `102334155` — naive হলে এটা কোটি কোটি call নিত। শেষ assert প্রথম 8টা Fibonacci মিলিয়ে দেখে, তারপর print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function fibNaive(n) {
if (n <= 1) return n; // base case: F(0)=0, F(1)=1
return fibNaive(n - 1) + fibNaive(n - 2);
}
function fibMemo(n, cache = new Map()) { // manual cache — জাদুটা দেখার জন্য
if (cache.has(n)) return cache.get(n);
if (n <= 1) return n;
const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache.set(n, result);
return result;
}
// ---- test cases ----
assert(fibNaive(0) === 0, "base 0");
assert(fibNaive(1) === 1, "base 1");
assert(fibNaive(2) === 1, "fib 2");
assert(fibNaive(10) === 55, "fib 10");
assert(fibMemo(20) === 6765, "fib 20");
assert(fibMemo(30) === 832040, "fib 30");
assert(fibMemo(40) === 102334155, "fib 40 (দ্রুত)"); // naive হলে কোটি call
assert(JSON.stringify([...Array(8).keys()].map(fibNaive)) === JSON.stringify([0, 1, 1, 2, 3, 5, 8, 13]), "first 8");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এর `@lru_cache`-এর সরাসরি কোনো decorator JS-এ নেই, তাই memoization হাতে করি — একটা `Map` cache pass করে। default parameter `cache = new Map()` সুবিধাজনক, কিন্তু খেয়াল রেখো এটা **প্রতিটা top-level call**-এ নতুন map বানায় (Python-এর mutable-default ফাঁদ এখানে উল্টো — বরং নিরাপদ)। `cache.has(n)` দিয়ে আগে check করা লাইনটাই O(2^n)-কে O(n) করে দেয়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function fibNaive(n: number): number {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
function fibMemo(n: number, cache: Map