001 — Fibonacci Number¶

Source¶

Original source: Classic recursion exercise
Platform: LeetCode — https://leetcode.com/problems/fibonacci-number/
Topic: recursion (decrease-and-conquer → memoization)
Difficulty: Easy
Pattern: decrease-and-conquer, দুটো recursive call → recursion tree
Basic idea inherited from: loops; recursion tree-র ছবি

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।

index : 0  1  2  3  4  5  6   7
value : 0  1  1  2  3  5  8  13

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/-এর hash-map lookup pattern — n → F(n)। এই O(1) lookup-টাই exponential কাজকে linear-এ নামিয়ে আনে, কারণ প্রতিটা আলাদা subproblem তখন ঠিক একবার solve হয়।

6. Real-life analogy¶

একটা পারিবারিক গাছ ভাবো যেখানে প্রতিটা সংখ্যার "জন্ম" তার ঠিক আগের দুই পূর্বপুরুষ থেকে। তুমি যদি প্রতিবার পুরো বংশতালিকা নতুন করে গুনে দেখো, একই পূর্বপুরুষকে বহুবার গুনবে। কিন্তু একটা নোটবুকে (cache) প্রতিজনের নাম একবার লিখে রাখলে, পরেরবার শুধু খুলে দেখলেই হয় — দুবার গোনা লাগে না।

7. Visual explanation¶

দুটো recursive call হওয়ায় call-গুলো tree বানায়। fib(4)-এর tree:

                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-এ রাখো, পরেরবার শুধু তুলে আনো।

8. Example input and output¶

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

9. Brute force thinking¶

প্রথম সরল চিন্তা: সংজ্ঞাটা হুবহু code-এ নামিয়ে দাও — base case দুটো, তারপর দুটো recursive call যোগ করো।

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/-এ।

13. Thinking tweak¶

মোচড়: "কীভাবে দ্রুত করব?" ভাবার বদলে জিজ্ঞেস করো "একই subproblem কি দুবার compute হচ্ছে?" হ্যাঁ হলে — শুধু উত্তরটা মনে রাখো। এক লাইনের cache check পুরো exponential tree-টাকে একটা linear chain-এ বদলে দেয়।

14. Step-by-step dry run¶

Memoized fib(5):

fib(5) চায় fib(4) ও fib(3)।
fib(4) চায় fib(3) ও fib(2); fib(3) চায় fib(2) ও fib(1)।
সবচেয়ে গভীরে: fib(1) = 1, fib(0) = 0 — base case, cache-এ যায়।
ফিরতি পথে: fib(2) = 1 (cache), fib(3) = 2 (cache), fib(4) = 3 (cache)।
fib(5) = fib(4) + fib(3) = 3 + 2 = 5। প্রতিটা fib(k) ঠিক একবার compute হলো।

15. Python solution¶

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 করো, যাতে পরের বার শুধু তুলে আনা যায়।

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!।

18. Time complexity¶

Naive: O(2^n) — tree-তে ~2^n node। Memoized: O(n) — প্রতিটা subproblem F(0)..F(n) ঠিক একবার compute হয়।

19. Space complexity¶

O(n) — call stack-এর গভীরতা n পর্যন্ত যায়, আর cache-এ n+1টা value জমে।

20. Common mistakes¶

base case ভুলে যাওয়া বা শুধু n == 0 রাখা — তখন F(1) infinite recurse করে।
n - 2 ছাড়া শুধু n - 1 দিয়ে recurse করা — তখন এটা আর Fibonacci থাকে না।
mutable default argument cache={} ব্যবহার করা — call-এর মধ্যে state leak করে; cache=None দিয়ে guard করো।
naive version দিয়ে বড় n চালানো — timeout; cache যোগ করো।

21. Which basic problem this inherits from¶

ভিত্তি: loop দিয়ে running-sum ধরে রাখা + concept.md-র recursion tree। ../concept.md-তে fib tree আর ../patterns.md-এর Pattern 1 (decrease-and-conquer) ও Pattern 7 (memoization) দেখো — এই note ওই দুটোর সংযোগস্থল।

22. Similar harder problems¶

Climbing Stairs (ছদ্মবেশে Fibonacci) — https://leetcode.com/problems/climbing-stairs/ (এই tracker-এর #2)
House Robber (memoization-এর পরের ধাপ) — https://leetcode.com/problems/house-robber/
N-th Tribonacci Number — https://leetcode.com/problems/n-th-tribonacci-number/

23. Pattern learned¶

Decrease-and-conquer + memoization: recursive সংজ্ঞা সরাসরি code-এ নামাও, তারপর repeated subproblem দেখলে একটা cache দিয়ে exponential-কে linear করো — এটাই dynamic programming-এর প্রবেশদ্বার।

24. Final summary¶

ভবিষ্যতের আমাকে: "Fibonacci = দুটো base case + F(n-1)+F(n-2); tree-তে node repeat দেখলেই cache বসাও।" যখনই কোনো problem-এর উত্তর তার ঠিক আগের কয়েকটা উত্তরের যোগফল, আর recursion tree-তে একই node বারবার আসে — এই decrease-and-conquer → memoization জোড়াটা মনে করবে।

25. JavaScript solution (with test cases)¶

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) করে দেয়।

26. TypeScript solution (with test cases)¶

function fibNaive(n: number): number {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

function fibMemo(n: number, cache: Map<number, number> = new Map()): number {
  const hit = cache.get(n);
  if (hit !== undefined) return hit;        // cache hit
  if (n <= 1) return n;
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(fibNaive(10), 55, "naive 10");
expect(fibMemo(20), 6765, "memo 20");
expect(fibMemo(40), 102334155, "memo 40");
expect(fibNaive(0), 0, "base0");
expect(fibNaive(1), 1, "base1");
console.log("সব TS test pass!");

TS টীকা: Map<number, number> generic-এ cache-এর key ও value দুটোই number-এ বাঁধা। const hit = cache.get(n); if (hit !== undefined) প্যাটার্নে TypeScript number | undefined-কে narrow করে — সরাসরি if (cache.get(n)) লিখলে F(0)=0 (falsy!) cache-hit সত্ত্বেও miss হিসেবে গণ্য হতো, তাই !== undefined জরুরি। return type number স্পষ্ট রাখে এটা সবসময় একটা সংখ্যা ফেরায়।

27. কোথায় কাজে লাগে (real-world use)¶

Memoization/DP-র প্রবেশদ্বার: যেকোনো overlapping-subproblem সমস্যায় (knapsack, edit-distance, coin-change) এই cache-চিন্তা মূল ভিত্তি।
Caching expensive computation: pure function-এর result cache করে পুনরায় গণনা এড়ানো — সর্বত্র performance pattern।
Algorithm analysis শেখা: exponential vs linear-এর জীবন্ত উদাহরণ, recursion tree বোঝার আদর্শ মডেল।
Financial/growth modeling: Fibonacci ও সম্পর্কিত recurrence (compound growth, population) মডেলিং-এ আসে।
Procedural generation: golden-ratio/Fibonacci sequence UI layout, art, ও nature-simulation-এ ব্যবহৃত।

এক কথায়, "উত্তর = আগের কয়েকটা উত্তরের ফল, আর একই subproblem বারবার আসছে" — দেখলেই memoization/DP; Fibonacci সেই pattern শেখার canonical প্রথম problem।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।