06 — Recursion and Backtracking

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 — এটা কখনো একই dead end দুবার ঘোরে না, আর কোনো guess undo করতে ভোলে না।

বাস্তব 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/ — call stack নিজেই একটা stack; recursion গোপনে যে data structure ব্যবহার করে, ওই section সেটাই বোঝায়।

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

• Stack কী (LIFO) — recursion-এর frame-গুলো একটার উপরেই থাকে।
• Function argument কীভাবে local হয়: প্রতিটা call parameter-এর নিজস্ব copy পায়।
• 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	Source	Pattern
Fibonacci Number	https://leetcode.com/problems/fibonacci-number/	Decrease-and-conquer → memoization
Climbing Stairs	https://leetcode.com/problems/climbing-stairs/	Decrease-and-conquer → memoization
Reverse String	https://leetcode.com/problems/reverse-string/	Decrease-and-conquer (two-end recursion)
Power of Two	https://leetcode.com/problems/power-of-two/	Decrease-and-conquer (divide by 2)
Pow(x, n)	https://leetcode.com/problems/powx-n/	Divide-and-conquer (fast power)

Medium

Problem	Source	Pattern
Subsets	https://leetcode.com/problems/subsets/	Include/exclude branch
Subsets II	https://leetcode.com/problems/subsets-ii/	Include/exclude + duplicate skipping
Permutations	https://leetcode.com/problems/permutations/	Choose each remaining
Permutations II	https://leetcode.com/problems/permutations-ii/	Choose remaining + duplicate skipping
Combination Sum	https://leetcode.com/problems/combination-sum/	Combinations with pruning
Combination Sum II	https://leetcode.com/problems/combination-sum-ii/	Pruning + duplicate handling
Generate Parentheses	https://leetcode.com/problems/generate-parentheses/	Constraint backtracking (counts as validity)
Letter Combinations of a Phone Number	https://leetcode.com/problems/letter-combinations-of-a-phone-number/	Cartesian choose-explore
Word Search	https://leetcode.com/problems/word-search/	Grid backtracking with visited marks
Palindrome Partitioning	https://leetcode.com/problems/palindrome-partitioning/	Cut-point backtracking

Hard

Problem	Source	Pattern
N-Queens	https://leetcode.com/problems/n-queens/	Constraint backtracking
Sudoku Solver	https://leetcode.com/problems/sudoku-solver/	Constraint backtracking
Word Search II	https://leetcode.com/problems/word-search-ii/	Backtracking + trie (পরের section-গুলোর preview)
CSES "Chessboard and Queens"	https://cses.fi/problemset/ (task name: Chessboard and Queens)	N-Queens with blocked cells
CSES "Creating Strings"	https://cses.fi/problemset/ (task name: Creating Strings)	Permutations with duplicates

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: default recursion limit প্রায় 1000; গভীর recursion-এ sys.setrecursionlimit লাগে, নয়তো iterative rewrite।

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

Source map

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