Recursion and Backtracking — The Concept¶

একটা বাস্তব জীবনের analogy দিয়ে শুরু করি¶

তুমি movie theater-এ বসে আছ, কোন row জানো না, কিন্তু row number জানতে চাও। সামনে থেকে নিজে গুনতে না গিয়ে তুমি সামনের জনকে টোকা দাও: "তুমি কোন row-তে?" সেও জানে না, তাই সে তার সামনের জনকে টোকা দেয়। প্রশ্নটা সামনে যেতে থাকে যতক্ষণ না row 1-এ পৌঁছায় — সেই মানুষটা জানে: "আমি row 1-এ।" উত্তরটা পেছনে ফিরে আসে: "আমি row 1" → "তাহলে আমি row 2" → "তাহলে আমি row 3" → ... যতক্ষণ না তোমার কাছে পৌঁছায়।

এটাই recursion:

প্রতিটা মানুষ অল্প একটু কাজ করে (1 যোগ করা)।
কঠিন অংশটা এমন কাউকে দেওয়া হয় যার কাছে problem-এর একটা ছোট version আছে।
একদম নিচে কাউকে উত্তরটা সরাসরি জানতেই হবে — সেটাই base case — নয়তো টোকাটোকি কখনো থামবে না।

Backtracking-এর জন্য কল্পনা করো চক আর সুতো নিয়ে একটা maze ঘোরা: প্রতিটা মোড়ে তুমি একটা করিডোর choose করো (দাগ দাও), পুরোটা explore করো, আর dead end হলে মোড়ে ফিরে এসে un-choose করো (দাগ মুছে দাও) পরের করিডোর try করার আগে। তুমি কখনো হারাও না, আর একই মোড় থেকে একই করিডোর দুবার ঘোরো না।

একটা function যেটা নিজেকেই call করে¶

def factorial(n):
    if n == 0:           # base case: known outright
        return 1
    return n * factorial(n - 1)   # delegate a SMALLER problem

দুটো উপাদান যেগুলো ছাড়া চলবেই না:

Base case — এমন একটা version যেটা recurse না করেই উত্তর দেওয়া যায়।
Progress — প্রতিটা recursive call-কে base case-এর দিকে এগোতেই হবে (এখানে n - 1)।

দুটোর যেকোনো একটা miss করলে call-গুলো কখনো থামবে না (RecursionError)।

Memory-র ছবি: call stack¶

প্রতিটা function call একটা frame পায় — একটা private বাক্স যেখানে তার নিজের parameter আর local-গুলো থাকে। Call যত nest হয় frame তত জমে, আর call return করলে pop হয়ে যায়। factorial(3)-এর জন্য:

calling phase (stack grows down ↓)          returning phase (stack shrinks ↑)

| factorial(3)  n=3 |                       | factorial(3)  n=3 | ← 3 * 2 = 6
| factorial(2)  n=2 |                       | factorial(2)  n=2 | ← 2 * 1 = 2
| factorial(1)  n=1 |                       | factorial(1)  n=1 | ← 1 * 1 = 1
| factorial(0)  n=0 | → returns 1           (popped, one by one)

ছবিটা যে key fact-গুলো শেখায়:

প্রতিটা frame-এর n আলাদা। factorial(2)-এর n-এ factorial(1) হাতই দেয় না।
Stack-টা আক্ষরিক অর্থেই একটা stack (LIFO) — data structure-টা নিজে দেখতে ../04-stack-and-queue/।
গভীরতার দাম memory: Python default-এ stack-কে প্রায় 1000 frame-এ আটকে দেয়।

Base case-এর শৃঙ্খলা¶

Base case-টা সবার আগে লেখো, কোনো recursive logic লেখার আগেই। Checklist:

Base case কি সবচেয়ে ছোট legal input-গুলো cover করে (প্রায়ই empty string, n == 0, null node)?
এটা কি ঠিক TYPE return করে (list-return-করা function-কে base case-এও list return করতে হবে, হয়তো empty)?
Recursive step কি কখনো base case টপকে যেতে পারে (যেমন 2 করে কমাতে কমাতে 0 পার হয়ে যাওয়া)? সন্দেহ হলে <= দিয়ে guard করো।

def sum_list(nums):
    if not nums:                    # base case first, smallest input
        return 0
    return nums[0] + sum_list(nums[1:])

[4, 7]-এর উপর dry run: sum_list([4,7]) = 4 + sum_list([7]) = 4 + (7 + sum_list([])) = 4 + (7 + 0) = 11।

The leap of faith¶

সবচেয়ে গুরুত্বপূর্ণ একটাই মানসিক দক্ষতা: factorial(n) লেখার সময় তুমি ধরে নাও factorial(n - 1) আগে থেকেই কাজ করে আর ঠিক উত্তর দেয়। তুমি তার ভেতরে trace করতে যাও না। তুমি শুধু verify করো:

base case ঠিক আছে, আর
ছোট call-টা ঠিক হলে, যেভাবে তুমি জোড়া লাগাচ্ছ সেটা একটা সঠিক বড় উত্তর দেয়।

এটা আসলে hoodie পরা mathematical induction। প্রতিটা nested call মনে মনে simulate করার চেষ্টাই recursion-কে অসম্ভব মনে করায় — leap of faith-ই সেটাকে সহজ মনে করায়। ছোট call-কে বিশ্বাস করো; শুধু নিজের frame-এর logic check করো।

Recursion tree¶

Function যখন দুই বা ততোধিক recursive call করে, call-গুলো একটা লাইন না হয়ে tree বানায়:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

                fib(4)
               /      \
          fib(3)      fib(2)
          /    \       /   \
      fib(2) fib(1) fib(1) fib(0)
      /    \
  fib(1) fib(0)

Node গুনে দেখো: fib(2) দুবার compute হয়, fib(1) তিনবার। Tree-তে মোটামুটি 2^n node — repeated subproblem থেকে exponential অপচয়। এই ছবিটা মনে রেখো; এটাই memoization-এর, আর পরে dynamic programming-এর (../12-dynamic-programming/) আসল motivation।

Backtracking = choose → explore → un-choose¶

Backtracking একটা shared path-এ টুকরো টুকরো করে candidate solution বানায়, প্রতিটা টুকরোর পর recurse করে আর পরে সেটা undo করে:

def backtrack(path, options):
    if is_complete(path):
        record(path[:])             # copy! the live path keeps changing
        return
    for option in valid_options(options, path):
        path.append(option)         # CHOOSE
        backtrack(path, options)    # EXPLORE
        path.pop()                  # UN-CHOOSE (restore for the next option)

Un-choose step-টাই একটা মাত্র list-কে search tree-র প্রতিটা branch-এর কাজে লাগায়। এটা ভুলে যাওয়াই backtracking-এর এক নম্বর bug: dead branch-এর choice পরের branch-এ leak করে।

ছোট্ট concrete example — "ab" থেকে repetition সহ সব 2-letter word:

def words(path, result):
    if len(path) == 2:
        result.append("".join(path))
        return
    for ch in "ab":
        path.append(ch)     # choose
        words(path, result) # explore
        path.pop()          # un-choose

Dry run: choose 'a' → choose 'a' → record "aa" → pop → choose 'b' → record "ab" → pop → pop → choose 'b' → ... result = ["aa","ab","ba","bb"]। একটা list, চারটা word, শূন্য leak।

Core invariants¶

প্রতিটা recursive call problem-টাকে কঠোরভাবে ছোট করে (ছোট n, ছোট list, কম free slot)।
প্রতিটা legal input থেকে base case-এ পৌঁছানো যায়।
Backtracking-এ প্রতিটা loop iteration-এর আগে আর পরে path হুবহু এক (choose-কে un-choose নিখুঁতভাবে undo করে)।
Record করা উত্তরগুলো snapshot (path[:]), কখনোই live path-এর reference না।

কখন recursion/backtracking ব্যবহার করবে¶

Data self-similar: trees, nested lists, file systems, grammars।
সব configuration enumerate করতে হবে: subsets, permutations, placements।
Divide-and-conquer খাপ খায়: অর্ধেকগুলো independent আর জোড়া লাগানো যায় (merge sort, fast power)।
Natural definition-টাই recursive (fib, GCD, tree height)।

কখন ব্যবহার করবে না¶

সাধারণ loop-এই কাজ হয় (Python-এ array-র sum recursively করা slow আর depth limit-এর ঝুঁকি)।
Python-এ depth ~1000 ছাড়াতে পারে — explicit stack দিয়ে iteration-এ convert করো।
Subproblem ব্যাপকভাবে overlap করে আর তোমার দরকার শুধু একটা উত্তর, সব configuration না → re-explore না করে memoize করো বা পুরো DP-তে যাও।
উত্তরের সংখ্যা astronomically বড় আর তোমার শুধু গুনতে হবে, list করতে না → formula বা DP খোঁজো।

Complexity table¶

Computation	Time	Space (stack)	Why
`factorial(n)`	O(n)	O(n)	প্রতি level-এ একটা call, n-টা level
naive `fib(n)`	O(2^n)	O(n)	~2^n node-এর tree, depth n
memoized `fib(n)`	O(n)	O(n)	প্রতিটা subproblem একবারই compute হয়
subsets of n items	O(n · 2^n)	O(n)	2^n subset, প্রতিটার copy-তে n পর্যন্ত খরচ
permutations of n items	O(n · n!)	O(n)	n!-টা ordering, প্রতিটার length n
N-Queens (n=8)	exponential, heavily pruned	O(n)	Pruning n^n tree-র বেশিরভাগটাই মেরে ফেলে

Dry run সহ দুটো snippet¶

Decrease-and-conquer: string reverse¶

def rev(s):
    if len(s) <= 1:
        return s
    return rev(s[1:]) + s[0]

"abc"-র উপর dry run: rev("abc") = rev("bc") + "a" = (rev("c") + "b") + "a" = ("c" + "b") + "a" = "cba"।

Divide-and-conquer: fast power¶

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x

power(2, 5)-এর dry run: লাগবে power(2,2) → লাগবে power(2,1) → লাগবে power(2,0)=1 → power(2,1)=1*1*2=2 → power(2,2)=2*2=4 → power(2,5)=4*4*2=32। Exponent 5-এর জন্য মাত্র 4টা call — O(n)-এর বদলে O(log n)।

এক বাক্যের সারমর্ম¶

Recursion: সবচেয়ে ছোট case সরাসরি solve করো, আর বাকি সবকিছুর জন্য এক ধাপ কাজ করে বাকিটায় নিজেকে বিশ্বাস করো; backtracking এর সাথে choose/explore/un-choose যোগ করে, যাতে একটা shared path দিয়েই সম্ভাবনার পুরো একটা tree হাঁটা যায়।

পরের file: visual-explanation.md — call-stack আর recursion-tree-র movie, frame by frame।