Recursion and Backtracking — Frame by Frame¶

দুটো movie: factorial(4)-এর জন্য call stack-এর শ্বাস-প্রশ্বাস, আর fib(4)-এর recursion tree যেটা নষ্ট হওয়া কাজ ফাঁস করে দেয়। তারপর একটা ছোট backtracking clip।

Movie 1: factorial(4)-এর call stack¶

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

এই frame-গুলোতে stack নিচের দিকে বাড়ে। প্রতিটা বাক্স এক একটা call-এর private frame।

Frame 1 — main, factorial(4) call করে¶

| factorial(4)  n=4  waiting on factorial(3) |

Frame 2 — factorial(4), factorial(3) call করে¶

| factorial(4)  n=4  waiting |
| factorial(3)  n=3  waiting on factorial(2) |

Frame 3 — আরো গভীরে¶

| factorial(4)  n=4  waiting |
| factorial(3)  n=3  waiting |
| factorial(2)  n=2  waiting on factorial(1) |

Frame 4 — সবচেয়ে গভীর বিন্দু: base case জ্বলে ওঠে¶

| factorial(4)  n=4  waiting |
| factorial(3)  n=3  waiting |
| factorial(2)  n=2  waiting |
| factorial(1)  n=1  waiting |
| factorial(0)  n=0  → hits base case, returns 1  |   <- the turnaround

চারটা frame কথার মাঝখানে জমে আছে, অপেক্ষায়। পঞ্চমটা তার উত্তর সরাসরি জানে।

Frames 5-8 — unwind (উত্তরগুলো বুদবুদের মতো উপরে ওঠে)¶

Frame 5:  factorial(1) resumes: 1 * 1 = 1   → returns 1, frame popped
| factorial(4)  n=4 |
| factorial(3)  n=3 |
| factorial(2)  n=2 |

Frame 6:  factorial(2) resumes: 2 * 1 = 2   → returns 2
| factorial(4)  n=4 |
| factorial(3)  n=3 |

Frame 7:  factorial(3) resumes: 3 * 2 = 6   → returns 6
| factorial(4)  n=4 |

Frame 8:  factorial(4) resumes: 4 * 6 = 24  → returns 24
(stack empty — done)

যা গেঁথে নেবে: গুণটা n * ... ঘটে উপরে ওঠার পথে, ছোট উত্তরটা ফিরে আসার পর। Stack-এর maximum height (5টা frame)-ই হলো O(n) space cost।

Movie 2: fib(4)-এর recursion tree — repeated subproblem ধরা¶

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

Factorial-এর সোজা লাইনের মতো না — প্রতি level-এ দুটো call একটা TREE বানায়। Call-গুলো আগে left subtree চালায় (depth-first):

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

Execution order (stack-এর pulse দেখো): fib(4) → fib(3) → fib(2) → fib(1)=1 → fib(0)=0 → fib(2)=1 → fib(1)=1 → fib(3)=2 → fib(2) আবার → fib(1)=1 → fib(0)=0 → fib(2)=1 → fib(4)=2।

তারা-চিহ্নিত node-গুলো: fib(2) পুরোপুরি দুবার recompute হয়। fib(5)-এ হতো তিনবার; duplication প্রতি level-এ মোটামুটি double হয় — সেটাই O(2^n) blowup।

একই tree, memoization সহ¶

উত্তরগুলো একটা dict-এ cache করো; দ্বিতীয়বারের request-গুলো instant lookup হয়ে যায়:

                     fib(4)
                    /      \
              fib(3)       (cache hit: 1)
             /     \
        fib(2)   (cache hit: 1)
        /    \
    fib(1) fib(0)

Tree-টা n-টা node-এর একটা single spine-এ ধসে পড়ে: O(2^n) → O(n)। এই ধসে-পড়া ছবিটাই dynamic programming-এর origin story (../12-dynamic-programming/)।

Movie 3: backtracking — choose/explore/un-choose দিয়ে [1, 2]-এর subsets¶

def subsets(i, path, nums, out):
    if i == len(nums):
        out.append(path[:])
        return
    path.append(nums[i])          # choose: include nums[i]
    subsets(i + 1, path, nums, out)
    path.pop()                    # un-choose
    subsets(i + 1, path, nums, out)   # explore: exclude nums[i]

সময়ের সাথে path (একটাই shared list) দেখো:

step  action                         path        recorded
 1    choose 1                       [1]
 2    choose 2                       [1, 2]
 3    i==2 → record                  [1, 2]      [1,2]
 4    un-choose 2                    [1]
 5    exclude 2 branch, i==2         [1]         [1]
 6    un-choose 1                    []
 7    exclude 1, choose 2            [2]
 8    i==2 → record                  [2]         [2]
 9    un-choose 2                    []
10    exclude 2 branch, i==2         []          []
      done                                       [[1,2],[1],[2],[]]

এই হাঁটাটা যে decision tree trace করল:

                   start
                include 1 / \ exclude 1
                       [1]   []
              incl 2 /  \ excl   incl 2 /  \ excl
                [1,2]   [1]        [2]     []

প্রতিটা leaf = একটা subset। প্রতিটা branch-এর পরে shared path তার choice-এর-আগের অবস্থায় ফিরে আসে — সেই symmetry-টাই (append তারপর pop) পুরো শৃঙ্খলা।

Movie 4: N-Queens-এর একটা dead end আর সেখান থেকে ফেরা (4x4 board)¶

প্রতি row-তে একটা queen বসাও; column/diagonal-এ clash চলবে না। Q = placed, . = empty।

Frame A: row 0, try col 0          Frame B: row 1 — cols 0,1 attacked,
                                            try col 2
   Q . . .                            Q . . .
   . . . .                            . . Q .
   . . . .                            . . . .
   . . . .                            . . . .

Frame C: row 2 — EVERY col          Frame D: backtrack! un-choose row 1,
attacked. Dead end.                          try its next col (3)
   Q . . .                            Q . . .
   . . Q .                            . . . Q
   x x x x   ← nowhere legal          . . . .
   . . . .                            . . . .

Frame D থেকে search চলতে থাকে (row 2 col 1 কাজ করে, row 3 dead-end হয়, শেষমেশ row-0-র queen নিজেই col 1-এ সরে যায়, আর solution [1, 3, 0, 2] হাজির হয়)। Clip-টার মূল কথা: row 2-র dead end শুধু row 1-এর choice-টাই undo করে — আগের সিদ্ধান্তগুলো বহাল থাকে যতক্ষণ না তাদের নিজেদের alternative ফুরিয়ে যায়। এটাই maze analogy-র "নিকটতম মোড়ে হেঁটে ফেরা" আচরণ।

এই movie-গুলো থেকে যা মনে রাখবে¶

নামার পথে call জমে; ওঠার পথে উত্তর compute হয়।
একাধিক recursive call = একটা tree; repeated node = exponential অপচয়; memoization tree-টা ধসিয়ে দেয়।
Backtracking প্রতিটা append-এর সাথে একটা pop-এর নিখুঁত জোড়া বেঁধে একটা path সব branch-এ ভাগ করে নেয়।
Dead end শুধু সবচেয়ে সাম্প্রতিক choice-টা undo করে — search-টা ধৈর্যশীল, আতঙ্কিত না।

পরের file: patterns.md — সাতটা named pattern, প্রতিটার সাথে worked example।