001 — Fibonacci Number

Problem link ও উৎস

• 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-র ছবি

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা সংখ্যা 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

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি হলো loops আর recursion tree-র ছবি। একটা loop দিয়ে তুমি দুটো আগের value ধরে রেখে সামনে এগোতে পারো — কিন্তু সংজ্ঞাটা নিজেই recursive (F(n) = F(n-1) + F(n-2)), তাই এটা recursion শেখার একদম প্রথম problem। এখানে function একবার নয়, দুবার নিজেকে call করে, তাই call-গুলো একটা লাইন না হয়ে একটা tree বানায়।

ভেতরের যুক্তি

লুকানো 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-এর জন্ম দেয়।

কী দিয়ে তথ্য রাখব

Naive version-এ কোনো extra data structure লাগে না — শুধু call stack। Optimized version-এ একটা dict (hash map) লাগে cache হিসেবে, যাতে compute করা প্রতিটা F(k) মনে রাখা যায়।

এটি কেন উপযুক্ত

Cache-টা একটা dict কারণ আমরা argument n দিয়ে key করে O(1)-তে আগের উত্তর তুলে আনতে চাই। এটাই ../../05-hashing/-এর hash-map lookup pattern — n → F(n)। এই O(1) lookup-টাই exponential কাজকে linear-এ নামিয়ে আনে, কারণ প্রতিটা আলাদা subproblem তখন ঠিক একবার solve হয়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

fib(n):
    n <= 1 হলে n ফেরত দাও
    নাহলে fib(n-1) + fib(n-2) ফেরত দাও

কোথায় বেশি কাজ হচ্ছে

এই naive version O(2^n) — কারণ tree-তে মোটামুটি 2^n node, আর একই subproblem বারবার নতুন করে compute হয়। fib(2) দুবার, fib(1) তিনবার... n বড় হলে এই অপচয় বিস্ফোরিত হয়: fib(30)-এ ~2.7 million call। একই কাজ বারবার করাটাই মূল রোগ।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: প্রতিটা F(k)-এর উত্তর শুধু k-এর উপর নির্ভর করে — pure function। তাই একবার F(k) বের করলে সেটা ধরে রাখলে আর কখনো নতুন করে compute করতে হয় না। Tree-র repeated node-গুলোকে এক-একটা cached value-তে collapse করে দেওয়া যায়।

আরও কম কাজে সমাধান

একটা cache (dict) রাখো। fib(n)-এ ঢোকার সাথে সাথে check করো cache-এ আছে কি না; থাকলে সাথে সাথে return। নাহলে compute করো, cache-এ রাখো, তারপর return। এতে প্রতিটা আলাদা subproblem ঠিক একবার compute হয় — exponential থেকে O(n)-এ নেমে আসে। এটাই top-down DP, আর এটাকে উল্টে একটা loop-এ table ভরলে তুমি পৌঁছে যাও ../../12-dynamic-programming/-এ।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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 হলো।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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

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

TypeScript

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 স্পষ্ট রাখে এটা সবসময় একটা সংখ্যা ফেরায়।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

• 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 যোগ করো।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• 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/

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

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