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

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

Base case — এমন একটা version যেটা recurse না করেই উত্তর দেওয়া যায়।
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/।
গভীরতার দাম 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 করো:

base case ঠিক আছে, আর
ছোট 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/) আসল 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¶

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