Recursion and Backtracking — call, উত্তর ও ফিরে আসা¶

Recursion-এ বড় কাজ ছোট call-কে দিই। Backtracking-এ একটি choice নিয়ে সামনে যাই; ফেরার সময় সেই choice undo করে পরের পথ দেখি। Call stack, decision tree ও বোর্ড—তিনভাবে এই চলাচল দেখা যায়।

1. Factorial: নামার সময় call, ফেরার সময় গুণ¶

Python

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

factorial(4) ডাকে factorial(3); একইভাবে 2, 1, 0 পর্যন্ত যাই। নিচের stack-এ নতুন call উপরে। প্রতিটি call তার নিজের n মনে রাখে।

factorial(4): সবচেয়ে গভীরে একসঙ্গে পাঁচটি call

শুরু · f(4) ডেকেছে f(3)-কে
↑ top · এখানেই push / pop
চিহ্নিত ঘর: f(3)
f(4)
f(4)-এর গুণ এখনও বাকি; আগে f(3)-এর উত্তর চাই।
গভীরতম অবস্থা · base case
↑ top · এখানেই push / pop
চিহ্নিত ঘর: f(0)
f(1)
f(2)
f(3)
f(4)
f(0) সরাসরি 1 ফেরত দেয়। বাকি চার call অপেক্ষা করছে।
f(0), f(1), f(2) ফেরার পরে
↑ top · এখানেই push / pop
চিহ্নিত ঘর: f(3)
f(4)
f(3) এখন f(2)-এর উত্তর 2 পেয়েছে; 3 × 2 করবে।
সব call শেষ
খালি
f(4)-এর উত্তর 24। Call stack-এর এই অংশ খালি।

সব call তৈরি হওয়ার ক্রম: f(4) → f(3) → f(2) → f(1) → f(0)। ফেরার প্রতিটি ধাপ:

যে call ফেরে	হিসাব	ফেরত মান	তখনও সক্রিয় call: পুরনো → নতুন
f(0)	base case	1	f(4), f(3), f(2), f(1)
f(1)	`1 × 1`	1	f(4), f(3), f(2)
f(2)	`2 × 1`	2	f(4), f(3)
f(3)	`3 × 2`	6	f(4)
f(4)	`4 × 6`	24	খালি

গুণ ঘটে ছোট call-এর উত্তর ফেরার পরে। মোট O(n) কাজ; সর্বোচ্চ n+1টি call সক্রিয়, তাই অতিরিক্ত stack space O(n)।

2. Fibonacci: একই ছোট কাজ দুবার হচ্ছে¶

Python

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

একটি call এখানে দুটি ছোট call করে। fib(4)-এর পূর্ণ call tree-তে fib(2) দুবার এসেছে:

flowchart TD
  F4["fib(4) = 3"] --> F3["fib(3) = 2"]
  F4 --> F2B["fib(2) = 1 · আবার"]
  F3 --> F2A["fib(2) = 1 · প্রথমবার"]
  F3 --> F1B["fib(1) = 1"]
  F2A --> F1A["fib(1) = 1"]
  F2A --> F0A["fib(0) = 0"]
  F2B --> F1C["fib(1) = 1"]
  F2B --> F0B["fib(0) = 0"]

Execution বাঁ শাখা আগে চালায়। নতুন call শুরু হওয়ার ক্রম: 4, 3, 2, 1, 0, 1, 2, 1, 0। প্রথম fib(2)-এর উত্তর 1 ফেরে; তা দিয়ে fib(3) হয় 2। তারপর ডান শাখায় fib(2) আবার পুরো কাজ করে; শেষে fib(4) = 2 + 1 = 3।

Naive পদ্ধতির সময় exponential: সহজ upper bound O(2ⁿ), আরও নির্দিষ্ট bound Θ(φⁿ) যেখানে φ≈1.618। কিন্তু stack space O(n)—পুরো tree একসঙ্গে stack-এ থাকে না, কেবল সক্রিয় পথটি থাকে।

Memoization: উত্তর পেলে cache-এ রাখো¶

প্রতিটি call-এর উত্তর, base case-সহ, cache করলে দ্বিতীয়বার আর ভেতরের শাখা চালাতে হয় না।

flowchart TD
  F4["fib(4)"] --> F3["fib(3)"]
  F4 --> C2["fib(2): cache থেকে 1"]
  F3 --> F2["fib(2)"]
  F3 --> C1["fib(1): cache থেকে 1"]
  F2 --> B1["fib(1) = 1 · রাখো"]
  F2 --> B0["fib(0) = 0 · রাখো"]

0 থেকে n—মোট n+1টি আলাদা subproblem। প্রতিটির উত্তর একবার হিসাব করায় সময় O(n), cache ও call stack মিলে অতিরিক্ত জায়গা O(n)। একই ধারণা Dynamic Programming-এ কাজে লাগবে।

3. Subsets: একটি choice, একটি undo¶

[1, 2]-এর প্রতিটি সংখ্যা রাখব অথবা বাদ দেব। path একটিই shared list; একটি branch থেকে ফিরে তার পরিবর্তন undo করি।

Python

def subsets(i, path, nums, out):
    if i == len(nums):
        out.append(path[:])          # এই অবস্থার আলাদা copy রাখো
        return
    path.append(nums[i])             # সংখ্যাটি নাও
    subsets(i + 1, path, nums, out)
    path.pop()                       # নেওয়ার সিদ্ধান্ত undo করো
    subsets(i + 1, path, nums, out)   # সংখ্যাটি না-নিয়ে দেখো

out = []
subsets(0, [], [1, 2], out)
assert out == [[1, 2], [1], [2], []]

flowchart TD
  S["শুরু · খালি path"] -->|"1 নাও"| A["[1]"]
  S -->|"1 বাদ"| B["খালি path"]
  A -->|"2 নাও"| C["[1, 2] · record"]
  A -->|"2 বাদ"| D["[1] · record"]
  B -->|"2 নাও"| E["[2] · record"]
  B -->|"2 বাদ"| F["[] · record"]

ধাপ	কাজ	কাজের পরে path	নতুন record
1	1 নাও	`[1]`	—
2	2 নাও	`[1,2]`	—
3	শেষ index: copy রাখো	`[1,2]`	`[1,2]`
4	2 undo	`[1]`	—
5	2 বাদ দেওয়া শাখায় record	`[1]`	`[1]`
6	1 undo	`[]`	—
7	1 বাদ দেওয়া শাখায় 2 নাও	`[2]`	—
8	শেষ index: copy রাখো	`[2]`	`[2]`
9	2 undo	`[]`	—
10	2 বাদ দেওয়া শাখায় record	`[]`	`[]`

প্রতিটি leaf একটি subset। path[:]-এর বদলে একই path object রাখলে পরের undo-তে সংরক্ষিত উত্তরও বদলে যাবে।

4. N-Queens: আর পথ না থাকলে আগের choice বদলাও¶

4×4 বোর্ডের প্রতি row-তে একটি queen চাই; একই column বা diagonal-এ দুটি queen চলবে না। Q বসানো queen, · খালি ঘর, × সেই row-তে নিষিদ্ধ ঘর। Row ও column দুটোই 0 থেকে গুনি।

একটি dead end থেকে ফিরে নতুন column চেষ্টা

১ · row 0, col 0-এ queen
চিহ্নিত ঘর: Q
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
পরের row-তে col 2 অথবা 3 নেওয়া যায়।
২ · row 1, col 2: সামনে পথ বন্ধ
চিহ্নিত ঘর: Q
·
·
·
·
·
চিহ্নিত ঘর: Q
·
ফাঁকা বা বাদ দেওয়া ঘর: ×
ফাঁকা বা বাদ দেওয়া ঘর: ×
ফাঁকা বা বাদ দেওয়া ঘর: ×
ফাঁকা বা বাদ দেওয়া ঘর: ×
·
·
·
·
row 2-এর কোনো column বৈধ নয়। এই branch শেষ।
৩ · row 1-এর choice undo; এবার col 3
চিহ্নিত ঘর: Q
·
·
·
·
·
·
চিহ্নিত ঘর: Q
·
·
·
·
·
·
·
·
এবার row 2-এ col 1 নেওয়া যায়; সেটিও পরে dead end হবে।

Column বাছার ক্রম 0, 1, 2, 3। নিচে প্রথম সমাধান পর্যন্ত সব বৈধ placement ও undo আছে; আক্রমণের মধ্যে পড়া column সঙ্গে সঙ্গে বাদ যায়। columns[i] হলো row i-এর queen-এর column।

ধাপ	কাজ	columns	পরের row-তে বৈধ column
1	row 0, col 0 বসাও	`[0]`	2, 3
2	row 1, col 2 বসাও	`[0,2]`	নেই
3	row 1-এর queen সরাও	`[0]`	পরের বিকল্প 3
4	row 1, col 3 বসাও	`[0,3]`	1
5	row 2, col 1 বসাও	`[0,3,1]`	নেই
6	row 2-এর queen সরাও	`[0,3]`	আর নেই
7	row 1-এর queen সরাও	`[0]`	আর নেই
8	row 0-এর queen সরাও	`[]`	পরের বিকল্প 1
9	row 0, col 1 বসাও	`[1]`	3
10	row 1, col 3 বসাও	`[1,3]`	0
11	row 2, col 0 বসাও	`[1,3,0]`	2
12	row 3, col 2 বসাও	`[1,3,0,2]`	সব row পূর্ণ: record

প্রথম সমাধান: columns = [1, 3, 0, 2]

চার queen, কোনো সংঘর্ষ নেই
·
চিহ্নিত ঘর: Q
·
·
·
·
·
চিহ্নিত ঘর: Q
চিহ্নিত ঘর: Q
·
·
·
·
·
চিহ্নিত ঘর: Q
·
সব উত্তর চাইলে এখানেও undo করে search চালাতে হবে। দ্বিতীয় সমাধান [2, 0, 3, 1]।

নিজে চেষ্টা করো: Subsets-এর tree-তে [1,2] record করার পরে কোন pop() চলে দেখাও। তারপর N-Queens-এ [0,3,1] থেকে কেন ফিরতে হয়, শেষ row-এর চার column পরীক্ষা করে বোঝাও। পরের পাঠ: patterns।