# 06 — Recursion and Backtracking

## এখান থেকে শুরু করো

প্রথমে [ধারণা](concept.md), তারপর [সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ](visual-explanation.md), তারপর [কোন প্রশ্নে কোন pattern](patterns.md) পড়ো। [সমস্ত problem ও বাংলা নোট](problems/README.md) এবং [উৎসের তালিকা](source-map.md) সরাসরি খোলা যাবে।

| ধাপ | কী শিখবে | প্রথম অনুশীলন |
| --- | --- | --- |
| 1 | base case ও return | [Fibonacci](problems/001-fibonacci-number.md) |
| 2 | input অর্ধেক করা | [Fast Power](problems/005-pow-x-n.md) |
| 3 | নেব কি নেব না | [Subsets](problems/007-subsets.md) |
| 4 | প্রতিটি unused বিকল্প | [Permutations](problems/009-permutations.md) |
| 5 | অসম্ভব branch বাদ | [Combination Sum](problems/012-combination-sum.md) |
| 6 | grid-এ choose ও undo | [Word Search](problems/017-word-search.md) |
| 7 | একাধিক constraint | [N-Queens](problems/019-n-queens.md) |

প্রতিটি ধাপে আগে ছোট input নিজে আঁকো, তারপর code লেখো। পরের ধাপে যাওয়ার আগে বলো: **কোন তথ্য রাখছি, প্রতি ধাপে কোন নিয়ম ঠিক থাকছে, এবং কাজের মোট খরচ কত?**

## বাস্তব প্রোগ্রামে সিদ্ধান্ত নেওয়া

| প্রোগ্রামে দরকার | state | base case / থামার শর্ত | কেন recursion মানায় |
| --- | --- | --- | --- |
| nested folder-এর মোট file size | বর্তমান folder | file হলে তার size | প্রতিটি child folder-এ একই কাজ |
| JSON/UI tree-এর প্রতিটি node দেখা | বর্তমান node | child নেই | একই গঠন ছোট আকারে পুনরাবৃত্ত |
| ছোট timetable-এর বৈধ সব assignment | বেছে নেওয়া slot ও ব্যবহৃত resource | সব কাজ বসানো হয়েছে | conflict হলেই branch বাদ |
| word puzzle-এ একটি path খোঁজা | cell, word index, এই path-এর visited | সব অক্ষর মিলে গেছে | প্রতিটি বৈধ প্রতিবেশী চেষ্টা করে undo |
| একই subproblem-এর উত্তর বারবার দরকার | উত্তর নির্ধারণকারী arguments | ছোট input-এর জানা উত্তর | memoization দিয়ে পুনর্গণনা এড়ানো যায় |

File-system traversal-এ symbolic link বা graph-এ cycle থাকলে visited tracking দরকার। অনেক গভীর input-এ Python recursion limit এড়াতে explicit stack ব্যবহার করো।


Recursion-ই প্রথম technique যেটা তোমাকে শুধু আলাদাভাবে code করতে না, আলাদাভাবে *ভাবতে* বলে। এখানে এটা master করো — trees, graphs, আর dynamic programming সব সহজ হয়ে যাবে।

## এই technique-টা কী?

Recursion হলো এমন একটা function যেটা একই problem-এর *ছোট version*-এর উপর নিজেকেই call করে problem solve করে — যতক্ষণ না version-টা এত ছোট হয় যে সরাসরি উত্তর দেওয়া যায় (সেটাই base case)।

Backtracking হলো steering wheel লাগানো recursion: প্রতিটা step-এ তুমি একটা option **choose** করো, তার পরিণতি recursively **explore** করো, তারপর **un-choose** (undo) করো যাতে পরের option-টা try করতে পারো। এটা প্রতিটা candidate solution-এ নিয়ম মেনে হাঁটে, আর candidate-দের মধ্যে কাজ ভাগ করে নেয়।

## কেন এটা আছে (কোন ব্যথাটা সারায়)

কিছু problem স্বভাবতই self-similar — "একটা folder-এ files আর folders থাকে, যেগুলোতে আবার files আর folders থাকে..." — আর loop দিয়ে এগুলো লিখতে গেলে pending কাজের stack তোমাকে নিজেই সামলাতে হয়। Recursion-এ language-ই সেই stack সামলায়, তাই code-টা problem-এর আকৃতির আয়না হয়ে যায়।

Backtracking আছে কারণ কিছু প্রশ্নের কোনো formula নেই: "সব valid seating-এর list দাও", "queen-দের এমনভাবে বসাও যেন কেউ কাউকে attack না করে"। একমাত্র সৎ পদ্ধতি হলো গোছানো trial and error, আর backtracking হলো নিখুঁত হিসাব-রাখা trial and error — সঠিক state ও undo নিয়ম রাখলে branch-গুলো আলাদা করে পরীক্ষা করা যায়। তবে আলাদা পথে একই state আবার আসতে পারে; duplicate handling বা memoization লাগবে কি না সেটাও ভাবতে হয়।

## বাস্তব software-এ কোথায় ব্যবহার হয়

- File-system walker, directory size calculator, recursive delete।
- Parser আর compiler (grammar recursive; JSON-ও তাই)।
- Constraint solver: Sudoku app, scheduling, register allocation।
- UI tree: nested component render করা একটা recursive walk।
- Game AI: move tree explore করা (minimax) হলো scoring সহ backtracking।

## Prerequisites

- Python-এ function, parameter, return value।
- List আর slicing।
- [../04-stack-and-queue/](../04-stack-and-queue/README.md) — call stack নিজেই একটা stack; recursion গোপনে যে data structure ব্যবহার করে, ওই section সেটাই বোঝায়।

## শেখার আগে কী revise করবে

- Stack কী (LIFO) — recursion-এর frame-গুলো একটার উপরেই থাকে।
- প্রতিটি call-এর parameter binding আলাদা; কিন্তু list-এর মতো mutable object একই reference দিয়ে পাঠালে একাধিক call একই object দেখে।
- List-এর `append` / `pop` — choose/un-choose mechanic ঠিক এ দুটোই ব্যবহার করে।

## Learning goals

- [ ] প্রতিবার, অন্য কিছু লেখার আগে একটা সঠিক base case লেখা।
- [ ] `factorial(4)`-এর call stack বাড়তে আর কমতে দেখে আঁকা।
- [ ] `fib(4)`-এর recursion tree এঁকে repeated subproblem-গুলোতে আঙুল রাখা।
- [ ] "Leap of faith" এক বাক্যে বলা আর দুশ্চিন্তা ছাড়া ব্যবহার করা।
- [ ] Include/exclude branch দিয়ে subsets implement করা।
- [ ] Choose-each-remaining দিয়ে permutations implement করা।
- [ ] Combination search-এ pruning যোগ করা আর কেন সেটা safe তা ব্যাখ্যা করা।
- [ ] একটা ছোট N-Queens solve করে choose → explore → un-choose গল্পের মতো বলা।
- [ ] Memoization কীভাবে exponential `fib`-কে linear বানায় তা ব্যাখ্যা করা (DP-র bridge)।

## Problem categories

| Category | One-line idea |
| --- | --- |
| Decrease-and-conquer | Input এক ধাপ ছোট করো; ছোট উত্তরটাকে বিশ্বাস করো |
| Divide-and-conquer | অর্ধেক করে ভাঙো; অর্ধেকগুলোর উত্তর জোড়া লাগাও |
| Subsets / include-exclude | প্রতিটা item-এর জন্য: নাও বা বাদ দাও (2^n leaves) |
| Permutations | প্রতিটা slot-এ যেকোনো unused item বেছে নাও (n! leaves) |
| Combinations with pruning | Subsets-এর মতো, কিন্তু যে branch জিততে পারবে না সেটা কেটে ফেলো |
| Constraint backtracking | বসাও, validity check করো, recurse করো, undo করো (N-Queens style) |
| Memoized recursion | Subproblem-এর উত্তর cache করো — DP-র দরজা |

## Practice list

### Easy

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Fibonacci Number | <https://leetcode.com/problems/fibonacci-number/> | Decrease-and-conquer → memoization | [নোট পড়ো](problems/001-fibonacci-number.md) |
| Climbing Stairs | <https://leetcode.com/problems/climbing-stairs/> | Decrease-and-conquer → memoization | [নোট পড়ো](problems/002-climbing-stairs.md) |
| Reverse String | <https://leetcode.com/problems/reverse-string/> | Decrease-and-conquer (two-end recursion) | [নোট পড়ো](problems/003-reverse-string.md) |
| Power of Two | <https://leetcode.com/problems/power-of-two/> | Decrease-and-conquer (divide by 2) | [নোট পড়ো](problems/004-power-of-two.md) |
| Pow(x, n) | <https://leetcode.com/problems/powx-n/> | Divide-and-conquer (fast power) | [নোট পড়ো](problems/005-pow-x-n.md) |

### Medium

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| Subsets | <https://leetcode.com/problems/subsets/> | Include/exclude branch | [নোট পড়ো](problems/007-subsets.md) |
| Subsets II | <https://leetcode.com/problems/subsets-ii/> | Include/exclude + duplicate skipping | [নোট পড়ো](problems/010-subsets-ii.md) |
| Permutations | <https://leetcode.com/problems/permutations/> | Choose each remaining | [নোট পড়ো](problems/009-permutations.md) |
| Permutations II | <https://leetcode.com/problems/permutations-ii/> | Choose remaining + duplicate skipping | [নোট পড়ো](problems/014-permutations-ii.md) |
| Combination Sum | <https://leetcode.com/problems/combination-sum/> | Combinations with pruning | [নোট পড়ো](problems/012-combination-sum.md) |
| Combination Sum II | <https://leetcode.com/problems/combination-sum-ii/> | Pruning + duplicate handling | [নোট পড়ো](problems/013-combination-sum-ii.md) |
| Generate Parentheses | <https://leetcode.com/problems/generate-parentheses/> | Constraint backtracking (counts as validity) | [নোট পড়ো](problems/015-generate-parentheses.md) |
| Letter Combinations of a Phone Number | <https://leetcode.com/problems/letter-combinations-of-a-phone-number/> | Cartesian choose-explore | [নোট পড়ো](problems/008-letter-combinations-phone.md) |
| Word Search | <https://leetcode.com/problems/word-search/> | Grid backtracking with visited marks | [নোট পড়ো](problems/017-word-search.md) |
| Palindrome Partitioning | <https://leetcode.com/problems/palindrome-partitioning/> | Cut-point backtracking | [নোট পড়ো](problems/016-palindrome-partitioning.md) |

### Hard

| Problem | Official task | Pattern | বাংলা ব্যাখ্যা |
| --- | --- | --- | --- |
| N-Queens | <https://leetcode.com/problems/n-queens/> | Constraint backtracking | [নোট পড়ো](problems/019-n-queens.md) |
| Sudoku Solver | <https://leetcode.com/problems/sudoku-solver/> | Constraint backtracking | [নোট পড়ো](problems/022-sudoku-solver.md) |
| Word Search II | <https://leetcode.com/problems/word-search-ii/> | Backtracking + trie (পরের section-গুলোর preview) | [নোট পড়ো](problems/023-word-search-ii.md) |
| CSES "Chessboard and Queens" | <https://cses.fi/problemset/task/1624/> (task name: Chessboard and Queens) | N-Queens with blocked cells | [নোট পড়ো](problems/021-cses-chessboard-and-queens.md) |
| CSES "Creating Strings" | <https://cses.fi/problemset/task/1622/> (task name: Creating Strings) | Permutations with duplicates | [নোট পড়ো](problems/018-cses-creating-strings.md) |

## Visualization ideas

- `factorial(4)`-এর জন্য থালার-stack animation: প্রতিটা call-এ একটা থালা, নামার সময় push, ওঠার সময় উত্তর লেখা অবস্থায় pop।
- `fib(5)`-এর recursion tree এঁকে প্রতিটা repeated node-এ গোল দাগ দাও — তারপর memoization দিয়ে আবার এঁকে দেখো tree-টা কীভাবে ধসে পড়ে।
- `[1,2,3]`-এর subsets-এর জন্য: একটা binary decision tree, left = include, right = exclude; 8টা leaf-ই হলো 8টা subset।
- 4x4 board-এ N-Queens: প্রতি row-তে একটা queen বসানো animate করো, attack হলে লাল X, আর আটকে গেলে queen ডানে সরে যাওয়া (সেটাই un-choose)।
- Recursion visualizer আছে <https://visualgo.net/en>-এ (recursion tree mode)।

## Common mistakes (সাধারণ ভুল)

- Base case নেই বা ভুল → `RecursionError: maximum recursion depth exceeded`।
- একই size-এর input-এ recurse করা (কোনো progress নেই) → infinite recursion।
- Choice undo করতে ভুলে যাওয়া (un-choose step) → এক branch-এর state অন্য branch-এ leak করে।
- Result-এ copy (`path[:]`)-র বদলে live `path` list-টাই append করা → সব result একটাই বদলাতে-থাকা list-কে alias করে।
- Leap of faith-এ ভরসা না রেখে প্রতিটা call মনে মনে trace করার চেষ্টা → 3 level-এর গভীরে গেলেই paralysis।
- Overlapping subproblem বারবার compute করা (naive `fib`), যেখানে এক লাইনের `@lru_cache` সব ঠিক করে দিত।
- Python-specific: recursion limit runtime অনুযায়ী দেখা যায় `sys.getrecursionlimit()` দিয়ে। বড় depth হলে explicit stack/iteration ভেবে দেখো; limit বাড়ালেই stack memory-এর সমস্যা মিটে যায় না।

## Interview problem-এর সাথে connection

"Generate all X" প্রশ্নগুলো (subsets, permutations, combinations, parentheses, partitions) big-tech interview loop-এর ধ্রুবতারা — এগুলো পরীক্ষা করে তুমি state পরিষ্কারভাবে সামলাতে পারো কি না। N-Queens-style placement-এর মতো constraint puzzle পরীক্ষা করে pruning-এর instinct। Interviewer-রা follow-up হিসেবে "now make it faster"-ও খুব ভালোবাসে — সেটাই ঠিক memoization-এর সেই DP bridge, যেটা দিয়ে এই folder শেষ হয়।

## Competitive programming-এর সাথে connection

- Complete search (recursion দিয়ে brute force) CP-র official প্রথম অস্ত্র: একই দর্শনের জন্য দেখো <https://usaco.guide/>-এর Bronze "Complete Search"।
- CSES Introductory Problems-এ সরাসরি backtracking task আছে (Chessboard and Queens, Creating Strings): <https://cses.fi/problemset/>।
- Pruning-এর মান-ই ঠিক করে exponential search time limit-এর মধ্যে pass করবে কি না।
- Recursion depth limit-এর জন্য Python-এ CP কঠিন হয় — iterative conversion-গুলো জেনে রেখো।

## Recommended learning order

1. [concept.md](concept.md) — call stack, base cases, leap of faith, choose/explore/un-choose।
2. [visual-explanation.md](visual-explanation.md) — `factorial(4)`-এর stack movie আর `fib(4)`-এর tree।
3. [patterns.md](patterns.md) — decrease-and-conquer থেকে DP bridge পর্যন্ত সাতটা named pattern।
4. [implementation.py](implementation.py) — চালাও; factorial, fib (naive vs memo), subsets, permutations, N-Queens পড়ো।
5. [problems/README.md](problems/README.md) — practice ladder, easy থেকে hard।

## Source map

এই folder-এর সব source, link আর copying status: দেখো [source-map.md](./source-map.md)।