# 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 করার আগে। কোন পথ বর্তমান search-এ ব্যবহার হয়েছে তা মনে রাখলে cycle এড়ানো যায়। একই state অন্য পথে আসতে পারে; তা বাদ দেওয়ার নিয়ম problem অনুযায়ী ঠিক করতে হয়।

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

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

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

1. **Base case** — এমন একটা version যেটা recurse না করেই উত্তর দেওয়া যায়।
2. **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/](../04-stack-and-queue/README.md)।
- গভীরতার দাম 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 করো।

```python
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`।

এই `sum_list` শেখার উদাহরণে প্রতি call-এ slice তৈরি হয়: মোট time ও peak auxiliary memory O(n²) হতে পারে। বড় list-এর জন্য loop বা index parameter ব্যবহার করো; শুধু recursion depth দেখে O(n) বলা যাবে না।

## The leap of faith

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

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

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

## Recursion tree

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

```python
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/](../12-dynamic-programming/README.md)) আসল motivation।

## Backtracking = choose → explore → un-choose

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

```python
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:

```python
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 a → choose b → record ab → pop b → pop a → choose b → choose a → record ba → pop a → choose b → record bb → pop b → pop b; result = `["aa","ab","ba","bb"]`। একটা list, চারটা word, শূন্য leak।

## Core invariants

1. প্রতিটা recursive call problem-টাকে কঠোরভাবে ছোট করে (ছোট `n`, ছোট list, কম free slot)।
2. প্রতিটা legal input থেকে base case-এ পৌঁছানো যায়।
3. Backtracking-এ প্রতিটা loop iteration-এর আগে আর পরে `path` হুবহু এক (choose-কে un-choose নিখুঁতভাবে undo করে)।
4. 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

```python
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"`।

উপরের `rev`-এ slicing এবং নতুন string জোড়া দেওয়ার জন্য মোট O(n²) সময় লাগে; pending slice-গুলোও O(n²) memory নিতে পারে। এটি recursion বোঝানোর ছোট উদাহরণ।

### Divide-and-conquer: fast power

```python
def power(x, n):
    if n < 0:
        if x == 0:
            raise ValueError("zero cannot have a negative exponent")
        return 1 / 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](./visual-explanation.md) — call-stack আর recursion-tree-র movie, frame by frame।