রিকার্শন — নিজেকে ডাকা ফাংশন আর call stack

১ · রিকার্শন কী — নিজের ছোট সংস্করণকে ডাকা

ধরুন কমলাপুর স্টেশনে ট্রেনের টিকিটের লম্বা লাইনে দাঁড়িয়ে আছেন। জানতে চান আপনি লাইনে কত নম্বরে। পেছন ফিরে সবাইকে গোনার উপায় নেই, সামনে অনেক মানুষ। তখন একটি সহজ কৌশল আছে: সামনের জনকে জিজ্ঞেস করুন, “ভাই, আপনি কত নম্বরে?” তিনিও জানেন না, তাই তিনি তাঁর সামনের জনকে একই প্রশ্ন করেন। প্রশ্নটি এভাবে সামনে এগোতে থাকে — যতক্ষণ না একেবারে কাউন্টারের সামনের মানুষটির কাছে পৌঁছায়। তিনি কাউকে জিজ্ঞেস না করেই বলেন, “আমি ১ নম্বর।” এবার উত্তর পেছনে ফিরতে থাকে: “আমি ২”, “আমি ৩”… শেষে আপনার সামনের জন বলেন “আমি ৪১”, আর আপনি বোঝেন আপনি ৪২ নম্বরে।

এটাই recursion (রিকার্শন)। একটি ফাংশন নিজের সমস্যার একটু ছোট সংস্করণ সমাধান করতে নিজেকেই ডাকে, তারপর সেই ছোট উত্তর থেকে নিজের উত্তর বানায়। লক্ষ করুন, এই কৌশল কাজ করে দুটি কারণে:

গণিতে এর সবচেয়ে পরিচিত উদাহরণ factorial: n! = n × (n − 1)!, আর 0! = 1 (বা 1! = 1). “৫-এর factorial কত?” জানতে হলে আগে জানতে হবে “৪-এর factorial কত?” — একই প্রশ্ন, ছোট আকারে। নিচের pseudocode-এ রিকার্সিভ ফাংশনের সাধারণ কাঠামো আর factorial দেখুন:

Pseudocode (যেকোনো রিকার্সিভ ফাংশনের কাঠামো)

SOLVE(problem):
    if problem is small enough:            // base case
        return the answer directly
    smaller = a smaller version of problem
    part = SOLVE(smaller)                   // recursive call (leap of faith)
    return COMBINE(part, problem)           // build the bigger answer

FACT(n):                                    // n >= 0
    if n <= 1: return 1
    return n * FACT(n - 1)

যেকোনো রিকার্সিভ সমাধান লেখার আগে তিনটি প্রশ্নের উত্তর নিজের কাছে পরিষ্কার রাখুন:

1. ফাংশনটি ঠিক কী ফেরত দেয়? এক বাক্যে বলুন — যেমন “fact(n) ফেরত দেয় n!”। এই চুক্তিটিই পরে বিশ্বাসের ভিত্তি।
2. সবচেয়ে ছোট কোন ইনপুটের উত্তর সরাসরি জানি? সেটিই base case. সব সম্ভাব্য ইনপুট যেন শেষমেশ এখানে পৌঁছায়।
3. সমস্যা প্রতিবার কি সত্যিই ছোট হচ্ছে? n থেকে n − 1, অ্যারের দৈর্ঘ্য অর্ধেক, string-এর একটি অক্ষর কম — কোনো একটি মাপ যেন প্রতিটি কলে কমে। এটিই termination-এর নিশ্চয়তা।

২ · Leap of faith — ছোট কলকে বিশ্বাস করুন

নতুনরা রিকার্শন বুঝতে গিয়ে প্রায়ই মাথার ভেতরে পুরো কল-শিকল চালানোর চেষ্টা করেন: “fact(5) ডাকে fact(4), সেটি ডাকে fact(3), সেটি…” — পাঁচ ধাপ পর্যন্ত চলে, কিন্তু Tower of Hanoi বা permutation-এ কয়েকশো কল মাথায় ধরে রাখা অসম্ভব। অভিজ্ঞ প্রোগ্রামাররা এটি করেন না। তাঁরা একটি মানসিক কৌশল ব্যবহার করেন, যার নাম “leap of faith” — বিশ্বাসের লাফ।

এটি অন্ধ বিশ্বাস নয় — এর পেছনে আছে mathematical induction, যা আপনি পর্ব ০৩-এ শুদ্ধতার প্রমাণে দেখেছেন। দুটি তুলনা করুন:

উদাহরণ — fact-এর শুদ্ধতার প্রমাণ। দাবি: সব n ≥ 0-এর জন্য fact(n) ফেরত দেয় n!।

• ভিত্তি: n = 0 বা 1 হলে ফাংশন 1 ফেরত দেয়, আর 0! = 1! = 1 — ঠিক।
• ধাপ: ধরি n ≥ 2, এবং fact(n − 1) ঠিকঠাক (n − 1)! ফেরত দেয় (induction-এর অনুমান)। তাহলে ফাংশন ফেরত দেয় n × (n − 1)! = n! — ঠিক।
• শেষ হওয়া: প্রতিটি কলে n এক করে কমে, আর n ≤ 1 হলেই থামে — তাই কলের সংখ্যা সসীম।

এই তিন লাইনের প্রমাণ দেখায় কেন leap of faith বৈধ। পরের অংশগুলোতে Tower of Hanoi বা subset তৈরির মতো জটিল রিকার্শনেও আমরা ঠিক এভাবেই ভাবব — “ছোট কাজটি হয়ে গেছে ধরে নিই, এখন আমার অংশটুকু কী?”

৩ · Call stack — প্রতিটি কলের নিজের খাতা

leap of faith দিয়ে লেখা সহজ হয়, কিন্তু কম্পিউটার আসলে কীভাবে এটি চালায়? একই ফাংশন একসাথে চারবার “চলছে” — প্রতিটির n আলাদা — তবু গুলিয়ে যায় না কেন?

উত্তর হলো call stack. প্রতিবার কোনো ফাংশন ডাকা হলে মেমরিতে তার জন্য একটি নতুন stack frame তৈরি হয় — যেন প্রতিটি কলের নিজের একটি খাতা। সেই খাতায় লেখা থাকে:

• এই কলের parameter (যেমন n = 3) আর local ভ্যারিয়েবল,
• return address — কাজ শেষে কাকে, কোন লাইনে উত্তর ফেরত দিতে হবে,
• অর্ধেক-করা কাজের অবস্থা — যেমন “ফেরত এলে 3 দিয়ে গুণ করতে হবে।”

খাতাগুলো রাখা হয় একটির ওপর আরেকটি — ঠিক অফিসের টেবিলে ফাইলের স্তূপের মতো। নতুন কল মানে স্তূপের ওপরে নতুন খাতা (push), কল শেষ মানে ওপরের খাতাটি সরানো (pop). যে শেষে এসেছে, সে আগে যায় — এটিই stack ডেটা স্ট্রাকচারের নিয়ম, যা পর্ব ১৩-এ বিস্তারিত দেখবেন।

নিচের ডায়াগ্রামে fact(4) চলার সময় stack কীভাবে বাড়ে আর কমে, দেখুন। “পরে” চাপুন:

1long long fact(int n) {2    if (n <= 1) return 1;      // base case3    return n * fact(n - 1);    // recursive case4}56int main() {7    cout << fact(4) << '\n';8}

এই ছবি থেকে রিকার্শনের দুটি খরচ পরিষ্কার হয়:

• সময় = মোট কলের সংখ্যা × প্রতিটি কলের ভেতরের কাজ। fact(n)-এ n টি কল, প্রতিটিতে O(1) কাজ, তাই Θ(n).
• জায়গা = সর্বোচ্চ গভীরতা × প্রতিটি frame-এর আকার। একসাথে সর্বোচ্চ n টি frame জমে, তাই বাড়তি জায়গা Θ(n) — যদিও একটি লুপ দিয়ে লিখলে লাগত মাত্র O(1). এই লুকানো খরচটি পরীক্ষায় প্রায়ই জিজ্ঞেস করা হয়।

৪ · fib(4) — recursion tree আর একই কাজ বারবার

factorial-এ প্রতিটি কল ঠিক একবার নিজেকে ডাকে, তাই কলগুলো একটি সরলরেখা। কিন্তু অনেক রিকার্শনে একটি কল দুই বা ততোধিকবার নিজেকে ডাকে। সবচেয়ে বিখ্যাত উদাহরণ Fibonacci সংখ্যা: F(0) = 0, F(1) = 1, আর F(n) = F(n − 1) + F(n − 2). সংজ্ঞাটি হুবহু কোডে লিখলে:

long long fib(int n) {
    if (n <= 1) return n;                // base cases: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);      // two recursive calls
}

দেখতে নিরীহ। কিন্তু প্রতিটি কল দুটি নতুন কল তৈরি করে, তাই কলগুলো আর রেখা নয় — একটি গাছ। একে বলে recursion tree: প্রতিটি কল একটি node, তার ভেতরের কলগুলো তার child. নিচে fib(4)-এর গাছ আর একই সময়ে call stack পাশাপাশি দেখুন। খেয়াল করুন — গাছ চওড়া হলেও stack কখনো গাছের উচ্চতার বেশি গভীর হয় না।

fib(4)-এ অপচয় সামান্য। কিন্তু n বাড়লে কী হয়? ধরি C(n) = fib(n) ডাকলে মোট কলের সংখ্যা। তাহলে C(0) = C(1) = 1, আর C(n) = 1 + C(n − 1) + C(n − 2). হিসাব করলে দেখা যায় C(n) = 2·F(n + 1) − 1 — অর্থাৎ কলের সংখ্যাও Fibonacci-র মতোই বাড়ে:

n মাত্র ১০ করে বাড়লে কলের সংখ্যা প্রায় ১২০ গুণ হয়ে যায়। fib(40)-এ ৩৩ কোটির বেশি কল — একটি সাধারণ ল্যাপটপে C++-এ কয়েক সেকেন্ড, Python-এ আধা মিনিট বা তার বেশি। fib(60)-এ কল কয়েক ট্রিলিয়ন — C++-এও ঘণ্টার পর ঘণ্টা, আর fib(100) হলে হাজার হাজার বছর! এটি exponential time: সময় Θ(φⁿ), যেখানে φ ≈ 1.618 (golden ratio). অথচ stack-এর জায়গা মাত্র Θ(n), কারণ যেকোনো মুহূর্তে শুধু একটি শাখা (মূল থেকে একটি পাতা পর্যন্ত পথ) stack-এ থাকে। সময় আর জায়গা এখানে সম্পূর্ণ আলাদা গল্প বলে।

৫ · Stack overflow, recursion depth আর tail recursion

Call stack অসীম নয়। প্রতিটি প্রোগ্রাম শুরুতেই stack-এর জন্য একটি নির্দিষ্ট জায়গা পায় — Linux-এ main thread-এর জন্য সাধারণত 8 MB, Windows-এ ডিফল্ট 1 MB. প্রতিটি frame যদি ধরুন ৫০ বাইট নেয়, তাহলে Windows-এ মোটামুটি বিশ হাজারের মতো গভীর রিকার্শনেই জায়গা শেষ। এই অবস্থার নাম stack overflow.

Tail recursion — শেষ কাজটিই যদি ডাক হয়

fact-এ return n * fact(n - 1); লাইনটি খেয়াল করুন। রিকার্সিভ কল ফেরার পরেও একটি কাজ বাকি থাকে — n দিয়ে গুণ। তাই frame-টিকে অপেক্ষায় রাখতেই হয়। কিন্তু যদি ডাকটাই একেবারে শেষ কাজ হয়?

// tail-recursive factorial: acc carries the partial product
long long fact_tail(int n, long long acc = 1) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, acc * n);   // nothing left to do after the call
}

এখানে গুণটি আগেই acc-এ করা হয়ে গেছে; রিকার্সিভ কল যা ফেরত দেবে, সেটিই হুবহু ফেরত যাবে। একে বলে tail recursion. এই অবস্থায় পুরোনো frame-এর আর কোনো কাজ নেই, তাই compiler চাইলে নতুন frame না বানিয়ে পুরোনোটিই আবার ব্যবহার করতে পারে — রিকার্শন কার্যত একটি লুপে পরিণত হয়, জায়গা লাগে O(1). এর নাম tail call optimization (TCO).

সারকথা: tail recursion একটি সুন্দর ধারণা, এবং “এটি একটি লুপের সমান” — এই উপলব্ধিটাই আসল লাভ। কিন্তু C++ বা Python-এ গভীরতার সমস্যার সমাধান হিসেবে এর ওপর ভরসা না করে সরাসরি লুপ লিখুন।

৬ · Fast power — অর্ধেক করে O(log n)

এবার এমন একটি রিকার্শন দেখি, যা লুপের চেয়ে দ্রুত সমাধান দেয়। x^e বের করতে সরল লুপে e বার গুণ লাগে। e = 10¹⁸ হলে সেটি অসম্ভব। কিন্তু একটি পর্যবেক্ষণ সব বদলে দেয়:

অর্থাৎ 3¹³ জানতে শুধু 3⁶ জানলেই চলে; 3⁶ জানতে 3³; 3³ জানতে 3¹; আর 3⁰ = 1 হলো base case. প্রতিটি ধাপে ঘাত অর্ধেক হয়ে যায়। এই কৌশলের নাম binary exponentiation বা fast power. Leap of faith দিয়ে ভাবুন: “power(x, e/2) ঠিক উত্তর দেবে — আমি শুধু সেটিকে বর্গ করব, বিজোড় হলে আরেকবার x দিয়ে গুণ করব।” নিচে 3¹³-এর হিসাব ধাপে ধাপে:

1long long power(long long x, int e) {2    ++calls;3    if (e == 0) return 1;              // base case4    long long half = power(x, e / 2);  // ONE call5    long long res = half * half;6    if (e % 2 == 1) res *= x;7    return res;8}

বিশ্লেষণ। প্রতিটি কলে e অন্তত অর্ধেক হয়, আর প্রতিটি কলে কাজ O(1) (একটি বা দুটি গুণ)। e ≥ 1 হলে মোট কল ঠিক ⌊log₂ e⌋ + 2 টি। তাই সময় Θ(log e), আর stack গভীরতাও Θ(log e). পর্ব ০৮-এ এটিকে recurrence হিসেবে লিখব: T(e) = T(e/2) + O(1) ⇒ T(e) = O(log e). এবার চালিয়ে দেখুন — তিনটি ভিন্ন ইনপুটে কতগুলো কল লাগে:

#include <iostream>
#include <utility>
using namespace std;

int calls = 0;

long long power(long long x, int e) {
    ++calls;
    if (e == 0) return 1;                  // base case
    long long half = power(x, e / 2);      // ONE recursive call
    long long res = half * half;
    if (e % 2 == 1) res *= x;              // odd exponent: one extra x
    return res;
}

int main() {
    for (auto [x, e] : {pair{3LL, 13}, pair{2LL, 62}, pair{10LL, 18}}) {
        calls = 0;
        long long r = power(x, e);
        cout << x << "^" << e << " = " << r << "  calls = " << calls
             << "  (naive loop: " << e << " multiplications)\n";
    }
}

3^13 = 1594323  calls = 5  (naive loop: 13 multiplications)
2^62 = 4611686018427387904  calls = 7  (naive loop: 62 multiplications)
10^18 = 1000000000000000000  calls = 6  (naive loop: 18 multiplications)

calls = 0

def power(x, e):
    global calls
    calls += 1
    if e == 0:                       # base case
        return 1
    half = power(x, e // 2)          # ONE recursive call
    res = half * half
    if e % 2 == 1:                   # odd exponent: one extra x
        res *= x
    return res

for x, e in [(3, 13), (2, 62), (10, 18)]:
    calls = 0
    r = power(x, e)
    print(f"{x}^{e} = {r}  calls = {calls}  (naive loop: {e} multiplications)")

3^13 = 1594323  calls = 5  (naive loop: 13 multiplications)
2^62 = 4611686018427387904  calls = 7  (naive loop: 62 multiplications)
10^18 = 1000000000000000000  calls = 6  (naive loop: 18 multiplications)

৭ · Tower of Hanoi — রিকার্শনের সবচেয়ে সুন্দর ধাঁধা

Tower of Hanoi-এর নিয়ম তিনটি। তিনটি খুঁটি A, B, C. A-তে n টি চাকতি, নিচে সবচেয়ে বড়, ওপরে সবচেয়ে ছোট। লক্ষ্য সবগুলো C-তে নেওয়া। (১) একবারে একটি চাকতি সরানো যায়, (২) শুধু ওপরের চাকতিটি সরানো যায়, (৩) বড় চাকতি কখনো ছোটটির ওপর রাখা যাবে না।

সরাসরি ভাবলে মাথা ঘুরে যায়। কিন্তু leap of faith দিয়ে ভাবুন — সবচেয়ে বড় চাকতিটির (n নম্বর) কথা ভাবুন। এটিকে C-তে নিতে হলে তার ওপরের n − 1 টি চাকতি অবশ্যই B-তে থাকতে হবে (A-তে থাকলে বড়টি ঢাকা, C-তে থাকলে বড়টি সেখানে বসতে পারবে না)। তাহলে সমাধান তিন লাইনের:

1. ওপরের n − 1 টি চাকতি A থেকে B-তে নিন (C-কে সাহায্যকারী ধরে) — এটি একই সমস্যা, এক চাকতি ছোট: বিশ্বাস করুন।
2. সবচেয়ে বড় চাকতিটি A থেকে C-তে নিন — একটি চাল।
3. B-র n − 1 টি চাকতি C-তে নিন (A-কে সাহায্যকারী ধরে) — আবার একই সমস্যা, আবার বিশ্বাস।

Base case: শূন্য চাকতি হলে কিছুই করার নেই। নিচে n = 3-এর পুরো সমাধান দেখুন। “চলমান কল” সারিতে খেয়াল করুন — কোন রিকার্সিভ কল কোন চালটি দিচ্ছে:

চাল কতগুলো? ধরি T(n) = n চাকতিতে চালের সংখ্যা। তিন ধাপের সমাধান থেকে T(0) = 0 এবং T(n) = 2·T(n − 1) + 1. দাবি: T(n) = 2ⁿ − 1. Induction দিয়ে প্রমাণ — ভিত্তি: T(0) = 0 = 2⁰ − 1. ধাপ: T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. ✔

এর চেয়ে কম কি সম্ভব? না — আর এটিও induction দিয়ে প্রমাণ করা যায়। যেকোনো সমাধানে সবচেয়ে বড় চাকতিটি অন্তত একবার সরাতেই হবে। প্রথমবার সরানোর মুহূর্তে বাকি n − 1 টি চাকতি তৃতীয় খুঁটিতে জড়ো থাকতে হবে, সেখানে নিতে অন্তত T(n − 1) চাল লাগে। বড়টিকে শেষবার সরানোর পর ওগুলোকে আবার তার ওপরে আনতে আরও অন্তত T(n − 1) চাল। তাই যেকোনো সমাধানে ≥ 2·T(n − 1) + 1 চাল — রিকার্সিভ সমাধানটিই সর্বোত্তম।

এবার আসল কোড — চালগুলো ছাপবে আর গুনবে:

#include <iostream>
using namespace std;

int moves = 0;

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;                 // base case: nothing to move
    hanoi(n - 1, from, via, to);        // 1) move n-1 disks out of the way
    ++moves;                            // 2) move the biggest disk
    cout << "Move disk " << n << ": " << from << " -> " << to << '\n';
    hanoi(n - 1, via, to, from);        // 3) put the n-1 disks back on top
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    cout << "Total moves: " << moves << " (2^3 - 1 = " << (1 << 3) - 1 << ")\n";
}

Move disk 1: A -> C
Move disk 2: A -> B
Move disk 1: C -> B
Move disk 3: A -> C
Move disk 1: B -> A
Move disk 2: B -> C
Move disk 1: A -> C
Total moves: 7 (2^3 - 1 = 7)

moves = 0

def hanoi(n, src, dst, via):
    global moves
    if n == 0:                       # base case: nothing to move
        return
    hanoi(n - 1, src, via, dst)      # 1) move n-1 disks out of the way
    moves += 1                       # 2) move the biggest disk
    print(f"Move disk {n}: {src} -> {dst}")
    hanoi(n - 1, via, dst, src)      # 3) put the n-1 disks back on top

hanoi(3, 'A', 'C', 'B')
print(f"Total moves: {moves} (2^3 - 1 = {2**3 - 1})")

Move disk 1: A -> C
Move disk 2: A -> B
Move disk 1: C -> B
Move disk 3: A -> C
Move disk 1: B -> A
Move disk 2: B -> C
Move disk 1: A -> C
Total moves: 7 (2^3 - 1 = 7)

৮ · আরও ক্লাসিক — উল্টানো, যোগফল, subset আর permutation

রিকার্শনের আসল দক্ষতা হলো সমস্যার ভেতরে “নিজের ছোট সংস্করণ” খুঁজে পাওয়া। কয়েকটি ক্লাসিক ধাঁচ দেখি — প্রতিটিতে প্রশ্ন একটাই: কোন মাপটি ছোট হচ্ছে, আর base case কী?

String উল্টানো আর অ্যারের যোগফল

// reverse s[i..j] in place: swap the ends, recurse on the middle
void rev(string& s, int i, int j) {
    if (i >= j) return;                  // 0 or 1 character left
    swap(s[i], s[j]);
    rev(s, i + 1, j - 1);
}

// sum of a[0..n-1] = sum of a[0..n-2] + a[n-1]
long long sum(const vector<int>& a, int n) {
    if (n == 0) return 0;                // empty array
    return sum(a, n - 1) + a[n - 1];
}

rev-এ প্রতি কলে string-এর দুই প্রান্ত থেকে একটি করে অক্ষর কমে: সময় Θ(n), stack গভীরতা প্রায় n/2. sum-এ প্রতি কলে অ্যারে এক ঘর ছোট: সময় Θ(n), গভীরতা n — তাই দশ লাখ ঘরের অ্যারেতে এটি stack overflow ঘটাতে পারে, যেখানে একটি সাধারণ লুপ কোনো সমস্যা ছাড়াই চলে।

সব subset তৈরি — প্রতিটি উপাদানে দুটি সিদ্ধান্ত

{1, 2, 3}-এর সব subset চাই। প্রতিটি উপাদানের সামনে দুটি পথ: “নেব না” বা “নেব”। প্রথম উপাদানের সিদ্ধান্ত নিয়ে বাকি উপাদানের জন্য একই প্রশ্ন রিকার্শনে পাঠাই — সমস্যা এক উপাদান ছোট। সব উপাদানের সিদ্ধান্ত হয়ে গেলে (base case) একটি subset সম্পূর্ণ।

a = [1, 2, 3]

def subsets(i, cur):
    if i == len(a):                  # base case: every element decided
        print(cur)
        return
    subsets(i + 1, cur)              # choice 1: skip a[i]
    subsets(i + 1, cur + [a[i]])     # choice 2: take a[i]

subsets(0, [])   # [] [3] [2] [2, 3] [1] [1, 3] [1, 2] [1, 2, 3]

এর recursion tree একটি পূর্ণ binary tree: উচ্চতা n, পাতা 2ⁿ টি — প্রতিটি পাতা একটি subset. প্রতিটি subset ছাপতে O(n), তাই মোট সময় Θ(n·2ⁿ), stack গভীরতা n + 1. এখানে সূচকীয় সময় কোনো ভুল নয় — উত্তরই 2ⁿ টি।

সব permutation — প্রতিটি ঘরে কে বসবে

// print every ordering of s[i..]; s[0..i-1] is already fixed
void permute(string& s, int i) {
    if (i == (int)s.size()) { cout << s << '\n'; return; }
    for (int j = i; j < (int)s.size(); ++j) {
        swap(s[i], s[j]);      // choose s[j] for position i
        permute(s, i + 1);     // arrange the rest (leap of faith)
        swap(s[i], s[j]);      // undo the choice
    }
}
// permute("abc") prints: abc acb bac bca cba cab

ঘর i-তে কে বসবে, সেটি একে একে বেছে নিয়ে বাকি ঘরগুলো রিকার্শনকে দিই। পাতা n! টি, মোট সময় Θ(n·n!)। লক্ষ করুন শেষ লাইনটি: রিকার্শন থেকে ফিরে এসে নিজের সিদ্ধান্ত ফিরিয়ে নেওয়া (undo). “চেষ্টা করো, ফিরে এসে আগের অবস্থায় ফেরাও, পরের বিকল্প চেষ্টা করো” — এই ধাঁচের নাম backtracking. পর্ব ৫৬-এ এর সাথে “অচল পথ আগেভাগে কেটে ফেলা” যোগ করে N-queens আর subset sum সমাধান করব।

আরেকটি বৈচিত্র্যও চিনে রাখুন: mutual recursion, যেখানে দুটি ফাংশন একে অপরকে ডাকে — যেমন গাণিতিক expression পার্স করতে expr() ডাকে term()-কে, আর বন্ধনী পেলে term() আবার expr()-কে।

৯ · Recursion বনাম iteration — নিজের stack দিয়ে রূপান্তর

প্রতিটি লুপকে রিকার্শনে লেখা যায়, আর প্রতিটি রিকার্শনকে লুপে — কারণ রিকার্শন আসলে “compiler যে stack সামলায়” তার ওপর চলা একটি লুপ। কখন কোনটি?

লেজের মতো সরল রিকার্শন (যেমন fact_tail) সহজেই লুপ হয়: parameter-গুলো হয়ে যায় লুপের ভ্যারিয়েবল। কিন্তু Hanoi বা DFS-এর মতো একাধিক রিকার্সিভ কল থাকলে কী করবেন? তখন compiler-এর call stack-এর কাজটি নিজেই করুন — একটি explicit stack রাখুন, যাতে থাকবে “এখনো যে কাজগুলো বাকি”। নিয়ম একটি: stack-এ উল্টো ক্রমে push করুন, কারণ শেষে যা ঢোকে, সেটিই আগে বের হয়।

// Tower of Hanoi without recursion: our own stack of pending tasks
struct Task { int n; char from, to, via; bool moveNow; };

void hanoi_iter(int n) {
    vector<Task> st{{n, 'A', 'C', 'B', false}};
    while (!st.empty()) {
        Task t = st.back(); st.pop_back();
        if (t.n == 0) continue;
        if (t.moveNow) {                      // the "middle" step: one real move
            cout << "Move disk " << t.n << ": " << t.from << " -> " << t.to << '\n';
            continue;
        }
        // push in REVERSE order of execution (last pushed runs first)
        st.push_back({t.n - 1, t.via, t.to, t.from, false});   // 3rd
        st.push_back({t.n, t.from, t.to, t.via, true});         // 2nd
        st.push_back({t.n - 1, t.from, t.via, t.to, false});   // 1st
    }
}

এটি হুবহু রিকার্সিভ সংস্করণের সাত লাইন আউটপুট দেয়। পার্থক্য: stack এখন heap মেমরিতে (vector), যার আকার কয়েক MB-র stack-সীমায় বাঁধা নয়। কনটেস্টে ১০^৫–১০^৬ node-এর গ্রাফে DFS (পর্ব ৪১) চালাতে ঠিক এই কৌশলই লাগে — বিশেষ করে Python-এ।

১০ · AI-এর যুগে রিকার্শন — বিশ্বাস করুন, কিন্তু যাচাই করে

“রিকার্সিভ ফাংশন লিখে দাও” বললে AI কয়েক সেকেন্ডে সুন্দর কোড দেয়। ছোট উদাহরণে প্রায় সবসময় চলে। সমস্যা লুকিয়ে থাকে কিনারায় — খালি ইনপুটে, বড় ইনপুটে, আর complexity-র দাবিতে। leap of faith আপনার নিজের লেখা কোডে বৈধ, কারণ আপনি base case আর ছোট হওয়ার নিয়ম যাচাই করেছেন; AI-এর কোডে সেই যাচাই আপনাকেই করতে হবে।

রিকার্শনে AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) রিকার্সিভ কোড যাচাইয়ের চেকলিস্ট

• সবচেয়ে ছোট ইনপুটে (0, খালি, এক উপাদান) চালিয়ে base case যাচাই করেছি
• প্রতিটি কলে কোন মাপটি ছোট হয়, এক বাক্যে বলতে পারি — তাই কোড অবশ্যই থামবে
• n = 3 বা 4-এ হাতে call stack trace করে ফল মিলিয়েছি
• counter বসিয়ে কলের সংখ্যা গুনেছি, আর দাবি করা complexity-র সাথে মিলিয়েছি
• সবচেয়ে খারাপ ইনপুটে stack গভীরতা হিসাব করেছি (Python-এ 1000-এর সীমা মাথায় রেখে)
• ছোট এলোমেলো ইনপুটে একটি সরল brute force সমাধানের সাথে মিলিয়ে stress testing করেছি