# Recursion and Backtracking — call, উত্তর ও ফিরে আসা

Recursion-এ বড় কাজ ছোট call-কে দিই। Backtracking-এ একটি choice নিয়ে সামনে যাই; ফেরার সময় সেই choice undo করে পরের পথ দেখি। Call stack, decision tree ও বোর্ড—তিনভাবে এই চলাচল দেখা যায়।

## 1. Factorial: নামার সময় call, ফেরার সময় গুণ

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

`factorial(4)` ডাকে `factorial(3)`; একইভাবে 2, 1, 0 পর্যন্ত যাই। নিচের stack-এ **নতুন call উপরে**। প্রতিটি call তার নিজের `n` মনে রাখে।

```dsa
kind: stack
title: "factorial(4): সবচেয়ে গভীরে একসঙ্গে পাঁচটি call"
steps:
  - label: "শুরু · f(4) ডেকেছে f(3)-কে"
    values: ["f(4)", "f(3)"]
    active: [1]
    note: "f(4)-এর গুণ এখনও বাকি; আগে f(3)-এর উত্তর চাই।"
  - label: "গভীরতম অবস্থা · base case"
    values: ["f(4)", "f(3)", "f(2)", "f(1)", "f(0)"]
    active: [4]
    note: "f(0) সরাসরি 1 ফেরত দেয়। বাকি চার call অপেক্ষা করছে।"
  - label: "f(0), f(1), f(2) ফেরার পরে"
    values: ["f(4)", "f(3)"]
    active: [1]
    note: "f(3) এখন f(2)-এর উত্তর 2 পেয়েছে; 3 × 2 করবে।"
  - label: "সব call শেষ"
    values: []
    note: "f(4)-এর উত্তর 24। Call stack-এর এই অংশ খালি।"
```

সব call তৈরি হওয়ার ক্রম: **f(4) → f(3) → f(2) → f(1) → f(0)**। ফেরার প্রতিটি ধাপ:

| যে call ফেরে | হিসাব | ফেরত মান | তখনও সক্রিয় call: পুরনো → নতুন |
| --- | --- | --- | --- |
| f(0) | base case | 1 | f(4), f(3), f(2), f(1) |
| f(1) | `1 × 1` | 1 | f(4), f(3), f(2) |
| f(2) | `2 × 1` | 2 | f(4), f(3) |
| f(3) | `3 × 2` | 6 | f(4) |
| f(4) | `4 × 6` | 24 | খালি |

গুণ ঘটে **ছোট call-এর উত্তর ফেরার পরে**। মোট O(n) কাজ; সর্বোচ্চ n+1টি call সক্রিয়, তাই অতিরিক্ত stack space **O(n)**।

## 2. Fibonacci: একই ছোট কাজ দুবার হচ্ছে

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

একটি call এখানে দুটি ছোট call করে। `fib(4)`-এর পূর্ণ call tree-তে `fib(2)` দুবার এসেছে:

```mermaid
flowchart TD
  F4["fib(4) = 3"] --> F3["fib(3) = 2"]
  F4 --> F2B["fib(2) = 1 · আবার"]
  F3 --> F2A["fib(2) = 1 · প্রথমবার"]
  F3 --> F1B["fib(1) = 1"]
  F2A --> F1A["fib(1) = 1"]
  F2A --> F0A["fib(0) = 0"]
  F2B --> F1C["fib(1) = 1"]
  F2B --> F0B["fib(0) = 0"]
```

Execution বাঁ শাখা আগে চালায়। নতুন call শুরু হওয়ার ক্রম: `4, 3, 2, 1, 0, 1, 2, 1, 0`। প্রথম fib(2)-এর উত্তর 1 ফেরে; তা দিয়ে fib(3) হয় 2। তারপর ডান শাখায় fib(2) আবার পুরো কাজ করে; শেষে **fib(4) = 2 + 1 = 3**।

Naive পদ্ধতির সময় exponential: সহজ upper bound **O(2ⁿ)**, আরও নির্দিষ্ট bound **Θ(φⁿ)** যেখানে φ≈1.618। কিন্তু stack space **O(n)**—পুরো tree একসঙ্গে stack-এ থাকে না, কেবল সক্রিয় পথটি থাকে।

### Memoization: উত্তর পেলে cache-এ রাখো

প্রতিটি call-এর উত্তর, base case-সহ, cache করলে দ্বিতীয়বার আর ভেতরের শাখা চালাতে হয় না।

```mermaid
flowchart TD
  F4["fib(4)"] --> F3["fib(3)"]
  F4 --> C2["fib(2): cache থেকে 1"]
  F3 --> F2["fib(2)"]
  F3 --> C1["fib(1): cache থেকে 1"]
  F2 --> B1["fib(1) = 1 · রাখো"]
  F2 --> B0["fib(0) = 0 · রাখো"]
```

0 থেকে n—মোট n+1টি আলাদা subproblem। প্রতিটির উত্তর একবার হিসাব করায় সময় **O(n)**, cache ও call stack মিলে অতিরিক্ত জায়গা **O(n)**। একই ধারণা [Dynamic Programming](../12-dynamic-programming/README.md)-এ কাজে লাগবে।

## 3. Subsets: একটি choice, একটি undo

`[1, 2]`-এর প্রতিটি সংখ্যা রাখব অথবা বাদ দেব। `path` একটিই shared list; একটি branch থেকে ফিরে তার পরিবর্তন undo করি।

```python
def subsets(i, path, nums, out):
    if i == len(nums):
        out.append(path[:])          # এই অবস্থার আলাদা copy রাখো
        return
    path.append(nums[i])             # সংখ্যাটি নাও
    subsets(i + 1, path, nums, out)
    path.pop()                       # নেওয়ার সিদ্ধান্ত undo করো
    subsets(i + 1, path, nums, out)   # সংখ্যাটি না-নিয়ে দেখো

out = []
subsets(0, [], [1, 2], out)
assert out == [[1, 2], [1], [2], []]
```

```mermaid
flowchart TD
  S["শুরু · খালি path"] -->|"1 নাও"| A["[1]"]
  S -->|"1 বাদ"| B["খালি path"]
  A -->|"2 নাও"| C["[1, 2] · record"]
  A -->|"2 বাদ"| D["[1] · record"]
  B -->|"2 নাও"| E["[2] · record"]
  B -->|"2 বাদ"| F["[] · record"]
```

| ধাপ | কাজ | কাজের পরে path | নতুন record |
| --- | --- | --- | --- |
| 1 | 1 নাও | `[1]` | — |
| 2 | 2 নাও | `[1,2]` | — |
| 3 | শেষ index: copy রাখো | `[1,2]` | `[1,2]` |
| 4 | 2 undo | `[1]` | — |
| 5 | 2 বাদ দেওয়া শাখায় record | `[1]` | `[1]` |
| 6 | 1 undo | `[]` | — |
| 7 | 1 বাদ দেওয়া শাখায় 2 নাও | `[2]` | — |
| 8 | শেষ index: copy রাখো | `[2]` | `[2]` |
| 9 | 2 undo | `[]` | — |
| 10 | 2 বাদ দেওয়া শাখায় record | `[]` | `[]` |

প্রতিটি leaf একটি subset। `path[:]`-এর বদলে একই `path` object রাখলে পরের undo-তে সংরক্ষিত উত্তরও বদলে যাবে।

## 4. N-Queens: আর পথ না থাকলে আগের choice বদলাও

4×4 বোর্ডের প্রতি row-তে একটি queen চাই; একই column বা diagonal-এ দুটি queen চলবে না। `Q` বসানো queen, `·` খালি ঘর, `×` সেই row-তে নিষিদ্ধ ঘর। Row ও column দুটোই 0 থেকে গুনি।

```dsa
kind: grid
title: "একটি dead end থেকে ফিরে নতুন column চেষ্টা"
steps:
  - label: "১ · row 0, col 0-এ queen"
    rows: [[Q, "·", "·", "·"], ["·", "·", "·", "·"], ["·", "·", "·", "·"], ["·", "·", "·", "·"]]
    active: [[0, 0]]
    note: "পরের row-তে col 2 অথবা 3 নেওয়া যায়।"
  - label: "২ · row 1, col 2: সামনে পথ বন্ধ"
    rows: [[Q, "·", "·", "·"], ["·", "·", Q, "·"], ["×", "×", "×", "×"], ["·", "·", "·", "·"]]
    active: [[0, 0], [1, 2]]
    muted: [[2, 0], [2, 1], [2, 2], [2, 3]]
    note: "row 2-এর কোনো column বৈধ নয়। এই branch শেষ।"
  - label: "৩ · row 1-এর choice undo; এবার col 3"
    rows: [[Q, "·", "·", "·"], ["·", "·", "·", Q], ["·", "·", "·", "·"], ["·", "·", "·", "·"]]
    active: [[0, 0], [1, 3]]
    note: "এবার row 2-এ col 1 নেওয়া যায়; সেটিও পরে dead end হবে।"
```

Column বাছার ক্রম 0, 1, 2, 3। নিচে প্রথম সমাধান পর্যন্ত **সব বৈধ placement ও undo** আছে; আক্রমণের মধ্যে পড়া column সঙ্গে সঙ্গে বাদ যায়। `columns[i]` হলো row i-এর queen-এর column।

| ধাপ | কাজ | columns | পরের row-তে বৈধ column |
| --- | --- | --- | --- |
| 1 | row 0, col 0 বসাও | `[0]` | 2, 3 |
| 2 | row 1, col 2 বসাও | `[0,2]` | নেই |
| 3 | row 1-এর queen সরাও | `[0]` | পরের বিকল্প 3 |
| 4 | row 1, col 3 বসাও | `[0,3]` | 1 |
| 5 | row 2, col 1 বসাও | `[0,3,1]` | নেই |
| 6 | row 2-এর queen সরাও | `[0,3]` | আর নেই |
| 7 | row 1-এর queen সরাও | `[0]` | আর নেই |
| 8 | row 0-এর queen সরাও | `[]` | পরের বিকল্প 1 |
| 9 | row 0, col 1 বসাও | `[1]` | 3 |
| 10 | row 1, col 3 বসাও | `[1,3]` | 0 |
| 11 | row 2, col 0 বসাও | `[1,3,0]` | 2 |
| 12 | row 3, col 2 বসাও | `[1,3,0,2]` | সব row পূর্ণ: record |

```dsa
kind: grid
title: "প্রথম সমাধান: columns = [1, 3, 0, 2]"
steps:
  - label: "চার queen, কোনো সংঘর্ষ নেই"
    rows: [["·", Q, "·", "·"], ["·", "·", "·", Q], [Q, "·", "·", "·"], ["·", "·", Q, "·"]]
    active: [[0, 1], [1, 3], [2, 0], [3, 2]]
    note: "সব উত্তর চাইলে এখানেও undo করে search চালাতে হবে। দ্বিতীয় সমাধান [2, 0, 3, 1]।"
```

**নিজে চেষ্টা করো:** Subsets-এর tree-তে `[1,2]` record করার পরে কোন `pop()` চলে দেখাও। তারপর N-Queens-এ `[0,3,1]` থেকে কেন ফিরতে হয়, শেষ row-এর চার column পরীক্ষা করে বোঝাও। পরের পাঠ: [patterns](./patterns.md)।