06 — Recursion and Backtracking

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

প্রথমে ধারণা, তারপর সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ, তারপর কোন প্রশ্নে কোন pattern পড়ো। সমস্ত problem ও বাংলা নোট এবং উৎসের তালিকা সরাসরি খোলা যাবে।

ধাপ	কী শিখবে	প্রথম অনুশীলন
1	base case ও return	Fibonacci
2	input অর্ধেক করা	Fast Power
3	নেব কি নেব না	Subsets
4	প্রতিটি unused বিকল্প	Permutations
5	অসম্ভব branch বাদ	Combination Sum
6	grid-এ choose ও undo	Word Search
7	একাধিক constraint	N-Queens

প্রতিটি ধাপে আগে ছোট 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/ — 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	নোট পড়ো
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	Official task	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	Official task	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/1624/ (task name: Chessboard and Queens)	N-Queens with blocked cells	নোট পড়ো
CSES "Creating Strings"	https://cses.fi/problemset/task/1622/ (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: 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 — 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।