C Recursion বাংলায় — নিজেকেই ডাকা ফাংশন | পর্ব ১৫

Q: রিকার্শন আর mathematical induction কি আসলে একই চিন্তা? তাহলে এটা দিয়ে কোড সঠিক প্রমাণ করা যায় কীভাবে?

হ্যাঁ — এরা একই মুদ্রার দুই পিঠ। Induction প্রমাণ করে, রিকার্শন হিসাব করে, কিন্তু কাঠামো হুবহু এক। Induction-এর ভিত্তি (base): কথাটি সবচেয়ে ছোট মানের জন্য সত্য। ↔ base case: সবচেয়ে ছোট ইনপুটে ফাংশন সরাসরি ঠিক উত্তর দেয়। Induction-এর ধাপ: k-এর জন্য সত্য হলে k + 1-এর জন্যও সত্য। ↔ recursive case: ছোট ডাক ঠিক উত্তর দিলে বড়টিও ঠিক উত্তর বানায়। উদাহরণ — Tower of Hanoi সঠিক, তা প্রমাণ করি। ০টি চাকতিতে কিছু না করাই ঠিক (ভিত্তি)। ধরে নিই n − 1টি চাকতি সঠিকভাবে সরানো যায় (ধাপের অনুমান)। তাহলে n টির জন্য: ওপরের n − 1টি B-তে সরানো বৈধ — কারণ নিচের বড় চাকতিটি তাদের সবার চেয়ে বড়, কোনো নিয়ম ভাঙে না। বড়টি C-তে যাওয়া বৈধ — C তখন খালি। তারপর n − 1টি C-তে বড়টির ওপর আনা বৈধ। প্রমাণ শেষ। একই সাথে চালের সংখ্যাও বেরিয়ে আসে: T(n) = 2·T(n − 1) + 1, যার সমাধান 2 n − 1. এই চিন্তা শুধু পরীক্ষার খাতায় নয়।

Q: সরল Fibonacci-তে n মাত্র ১০ বাড়ালে সময় কেন প্রায় ১২৩ গুণ হয়ে যায়?

সরল fib(n)-এ মোট ডাকের সংখ্যা গুনে দেখা যায়: C(n) = C(n − 1) + C(n − 2) + 1 — অর্থাৎ ডাকের সংখ্যাও নিজেই একটি Fibonacci-র মতো ধারা! সঠিক হিসাবে C(n) = 2 × fib(n + 1) − 1. fib(5)-এ ১৫, fib(30)-এ ২৬,৯২,৫৩৭, fib(40)-এ ৩৩,১১,৬০,২৮১ — ৩৩ কোটির বেশি। Fibonacci ধারায় পাশাপাশি দুটি সংখ্যার অনুপাত দ্রুত একটি নির্দিষ্ট মানের কাছে চলে যায় — প্রায় ১.৬১৮, যার নাম golden ratio. তাই n এক বাড়লে ডাক বাড়ে প্রায় ১.৬১৮ গুণ, আর n দশ বাড়লে ১.৬১৮ ১০ ≈ ১২৩ গুণ। (fib(30) থেকে fib(40)-এ ডাক সত্যিই প্রায় ১২৩ গুণ।) এমন বৃদ্ধিকে বলে exponential — প্রতিটি ধাপে গুণ, যোগ নয়। অনুভব করার জন্য: ধরুন আপনার কম্পিউটার সেকেন্ডে দশ কোটি ডাক সামলায়। fib(40) লাগবে কয়েক সেকেন্ড, fib(50)-এ ডাক প্রায় ৪ হাজার কোটি — কয়েক মিনিট। fib(80)-এ প্রায় দুই যুগ, আর fib(90)-এ হাজার বছরেরও বেশি। অথচ memo বা লুপে fib(90) লাগে নব্বইটির মতো ধাপ — চোখের পলকেরও কম।

Q: বাস্তবের কোন কোন সিস্টেম ভেতরে recursive? রিকার্শন কি শুধু পাঠ্যবইয়ের ধাঁধা?

মোটেই না। যেখানেই ডেটা “নিজের ভেতরে নিজে” — নেস্টেড — সেখানেই রিকার্শন স্বাভাবিকভাবে আসে। কয়েকটি উদাহরণ যা আপনি প্রতিদিন ব্যবহার করেন: ফাইল সিস্টেম: ফোল্ডারের ভেতরে ফাইল ও আরও ফোল্ডার। Windows-এ একটি ফোল্ডারের Properties-এ মোট মাপ দেখা, Linux-এ du বা rm -r (r মানে recursive!) — সবাই প্রতিটি সাব-ফোল্ডারে ঢুকে একই কাজ করে। ওয়েবপেজ: HTML-এ ট্যাগের ভেতরে ট্যাগ। ব্রাউজার পেজটিকে একটি গাছে (DOM) সাজায়, আর সেই গাছ ঘোরার স্বাভাবিক উপায় রিকার্শন। JSON: bKash বা যেকোনো অ্যাপের সার্ভার যে ডেটা পাঠায়, তাতে object-এর ভেতরে object, তালিকার ভেতরে তালিকা। JSON পড়ার প্রোগ্রাম (parser) প্রায়ই recursive. Compiler: (2 + (3 * (4 - 1))) — বন্ধনীর ভেতরে বন্ধনী। GCC ও Clang দুটোই কোড পড়তে হাতে লেখা “recursive descent parser” ব্যবহার করে: “expression মানে একটি term, তার পরে হয়তো + ও আরেকটি expression” — সংজ্ঞাটিই recursive.

এক নজরে · TL;DR

রিকার্শন মানে নিজেকে ডাকা: বড় সমস্যার উত্তর বের করতে ফাংশন একই সমস্যার একটু ছোট রূপের জন্য নিজেকেই আবার ডাকে।
দুটি অংশ বাধ্যতামূলক: base case (যেখানে থামবে) আর recursive case (যেখানে সমস্যা ছোট হয়ে আবার ডাক যায়)। প্রতিটি ডাক base case-এর দিকে এগোতেই হবে।
প্রতিটি ডাকে নতুন stack frame: ডাক যত গভীরে যায়, stack তত উঁচু হয়। base case না থাকলে বা ইনপুট বিশাল হলে হয় stack overflow.
সরল Fibonacci ভয়ংকর ধীর: একই উপ-সমস্যা বারবার হিসাব হয়। উত্তর লিখে রাখলে (memoization) প্রায় ২৭ লাখ ডাক নেমে আসে ৫৯-এ।
AI-এর যুগে: AI-এর লেখা রিকার্শনে আগে খুঁজুন — base case আছে কি, সেখানে পৌঁছায় কি, কত গভীরে যায়, আর একই কাজ বারবার হচ্ছে কি না।

এই পর্বে যা শিখবেন

রিকার্শনের মূল চিন্তা — বড় সমস্যাকে একই রকম ছোট সমস্যায় নামিয়ে আনা
যেকোনো recursive ফাংশন লেখার তিন প্রশ্নের ছক, আর গণিতের induction-এর সাথে এর মিল
ভেতরে call stack কীভাবে ওঠে-নামে, আর stack overflow কেন হয়
Fibonacci-র call tree দেখে বারবার একই কাজের অপচয় চেনা, আর memoization দিয়ে তা দূর করা
কখন রিকার্শন স্বাভাবিক পছন্দ, কখন লুপ ভালো — আর AI-এর লেখা রিকার্শন যাচাইয়ের চেকলিস্ট

১ · টিকিটের লাইনে একটি প্রশ্ন

ঈদের আগে কমলাপুর রেলস্টেশনে টিকিটের লম্বা লাইন। আপনি লাইনের অনেক পেছনে দাঁড়িয়ে। জানতে ইচ্ছে করছে — আপনার সামনে কয়জন আছেন? লাইন থেকে বের হয়ে গুনতে গেলে জায়গা হারাবেন। তাহলে উপায়?

উপায় খুব সহজ। আপনি সামনের মানুষটিকে জিজ্ঞেস করলেন, “ভাই, আপনার সামনে কয়জন?” তিনিও জানেন না, তাই তিনি ঠিক একই প্রশ্ন তাঁর সামনের জনকে করলেন। প্রশ্নটি এভাবে সামনে এগোতে থাকল। শেষে প্রশ্ন পৌঁছাল কাউন্টারের ঠিক সামনে দাঁড়ানো মানুষটির কাছে। তাঁর আর কাউকে জিজ্ঞেস করতে হলো না — তাঁর সামনে কেউ নেই, উত্তর শূন্য।

এরপর উত্তর ফিরতে শুরু করল। প্রত্যেকে পেছনের জনকে বললেন, “আমি যা শুনেছি, তার সাথে আমাকে যোগ করুন।” নিচের ডায়াগ্রামে “পরে” চাপুন — প্রশ্ন কীভাবে সামনে যায় আর উত্তর কীভাবে পেছনে ফেরে, খেয়াল করুন।

কাউন্টারলাইনের শুরু
রুমা
জামিল
তানিয়া
আপনি

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

এই ছোট্ট ঘটনায় রিকার্শনের পুরো চেহারা লুকিয়ে আছে। প্রত্যেক মানুষ একই নিয়ম মানছেন: “সামনে কেউ না থাকলে উত্তর ০; থাকলে সামনের জনের উত্তর + ১।” কোডে লিখলে প্রায় হুবহু এরকম:

int count_ahead(int position) {
    if (position == 1)                       // কাউন্টারের সামনে: base case
        return 0;
    return count_ahead(position - 1) + 1;    // সামনের জনকে একই প্রশ্ন
}

যে ফাংশন নিজের ভেতর থেকে নিজেকেই আবার ডাকে, তাকে বলা হয় recursive ফাংশন, আর পদ্ধতিটির নাম recursion (রিকার্শন)। শব্দটি এসেছে লাতিন recurrere থেকে, মানে “ফিরে দৌড়ানো” — উত্তর যে শেষে ফিরে আসে, সেই ছবিটিই এতে আছে।

আরও দুটি পরিচিত ছবি ভাবুন। বাক্সের ভেতর বাক্স: জন্মদিনে কেউ মজা করে একটি বড় বাক্স দিল। খুলে দেখেন ভেতরে আরেকটি বাক্স, তার ভেতরে আরেকটি… শেষে সবচেয়ে ছোট বাক্সে আসল উপহার। প্রতিবার আপনি একই কাজ করছেন — “বাক্স খোলো” — আর শেষ বাক্সটিই base case. মুখোমুখি দুটি আয়না: সেলুনে সামনে-পেছনে দুটি আয়না থাকলে ভেতরে ভেতরে অসংখ্য প্রতিবিম্ব দেখা যায়, যেন শেষই নেই। এটি এমন রিকার্শন, যার কোনো base case নেই। আয়নায় তবু আলো ক্ষীণ হয়ে একসময় মিলিয়ে যায়, কিন্তু কম্পিউটারে এমন রিকার্শন চলতেই থাকে, যতক্ষণ না মেমরি ফুরিয়ে প্রোগ্রাম ভেঙে পড়ে।

২ · দুটি অংশ: থামার জায়গা আর ছোট হওয়ার ধাপ

প্রতিটি সঠিক recursive ফাংশনের দুটি অংশ থাকে। একটি ছাড়া অন্যটি অর্থহীন।

🛑 Base case

সমস্যার সবচেয়ে ছোট রূপ, যার উত্তর সরাসরি জানা। এখানে ফাংশন নিজেকে আর ডাকে না, সোজা উত্তর ফেরত দেয়। ডাকাডাকির শিকল এখানেই থামে।

লাইনের সামনের জন: ০

🔁 Recursive case

সমস্যাটিকে একটু ছোট করে নিজেকে ডাকা, তারপর ফিরে আসা উত্তর দিয়ে নিজের উত্তর তৈরি করা। প্রতিটি ডাককে base case-এর একটু কাছে যেতেই হবে।

সামনের জনের উত্তর + ১

সবচেয়ে পরিচিত উদাহরণ factorial. ৪! মানে ৪ × ৩ × ২ × ১ = ২৪. খেয়াল করলে দেখবেন, ৪! আসলে ৪ × (৩!)। আর ৩! হলো ৩ × (২!)। অর্থাৎ যেকোনো n-এর factorial হলো n গুণ তার চেয়ে এক কম সংখ্যার factorial. এই সংজ্ঞাটিই সরাসরি কোড হয়ে যায়:

n! = 1, যদি n ≤ 1 (base case)
n! = n × (n − 1)!, অন্যথায় (recursive case)

যেকোনো recursive ফাংশন লেখার তিন প্রশ্ন

নতুনরা প্রায়ই রিকার্শন লিখতে গিয়ে মাথায় পুরো ডাকাডাকি কল্পনা করার চেষ্টা করেন — আর গুলিয়ে ফেলেন। তার দরকার নেই। শুধু তিনটি প্রশ্নের উত্তর দিন:

সবচেয়ে ছোট রূপ কোনটি, আর তার উত্তর কী? (factorial-এ: n ≤ 1 হলে উত্তর 1)
একটু ছোট সমস্যার উত্তর হাতে পেলে, বড়টির উত্তর কীভাবে বানাব? (n! = n × (n−1)!)
প্রতিটি ডাক কি নিশ্চিতভাবে base case-এর দিকে এগোচ্ছে? (n প্রতিবার ১ করে কমছে, তাই একসময় ১-এ পৌঁছাবেই)

মূল ধারণা

দ্বিতীয় প্রশ্নে একটি সাহসী ভাবনা লুকিয়ে আছে: ছোট সমস্যার ডাকটি ঠিক উত্তর দেবে — এটা ধরে নিন। সেটি কীভাবে উত্তর বের করবে, তা নিয়ে মাথা ঘামাবেন না। আপনার কাজ শুধু “ছোট উত্তর থেকে বড় উত্তর” বানানো, আর base case ঠিক রাখা। লাইনের মানুষটি যেমন পুরো লাইন গোনেন না — শুধু সামনের জনের কথায় বিশ্বাস রেখে ১ যোগ করেন।

এই বিশ্বাস অন্ধ নয়। এর পেছনে আছে একটি গাণিতিক প্রমাণ — যা আপনি পর্ব ০২-এ ডমিনোর গুটি দিয়ে দেখেছেন।

পর্ব ০২-এর ডমিনোর কথা মনে করুন: (১) প্রথম গুটি পড়বে, আর (২) কোনো গুটি পড়লে পরেরটিও পড়বে — তাহলে সব গুটিই পড়বে। একে বলে mathematical induction. রিকার্শন হুবহু একই যুক্তি, শুধু উল্টো দিক থেকে দেখা। base case হলো প্রথম গুটি: fact(1) ঠিক উত্তর দেয়। recursive case হলো দ্বিতীয় শর্ত: fact(n−1) ঠিক হলে fact(n) = n × fact(n−1)-ও ঠিক। দুটো মিলে প্রমাণ — যেকোনো n-এর জন্য fact(n) ঠিক উত্তর দেবে।

তৃতীয় প্রশ্নটি সবচেয়ে বেশি অবহেলিত। ধরুন কেউ লিখল: “n == 0 হলে থামো, নাহলে n − 2 দিয়ে নিজেকে ডাকো।” n = 6 দিলে 6 → 4 → 2 → 0, সব ঠিক। কিন্তু n = 5 দিলে 5 → 3 → 1 → −1 → −3 … শূন্যকে টপকে চলে গেল, আর কোনোদিন থামবে না! base case থাকা যথেষ্ট নয় — প্রতিটি ইনপুট থেকে সেখানে পৌঁছানো নিশ্চিত হতে হবে। এজন্য অভিজ্ঞরা লেখেন n <= 0, শুধু n == 0 নয়।

৩ · ভেতরে কী ঘটে — প্রতিটি ডাকে নতুন stack frame

পর্ব ১৩-এ দেখেছেন, কোনো ফাংশন ডাকা হলে মেমরির call stack-এ তার জন্য একটি নতুন stack frame তৈরি হয় — সেখানে থাকে প্যারামিটার, লোকাল ভ্যারিয়েবল আর কাজ শেষে কোথায় ফিরতে হবে তার ঠিকানা। রিকার্শনে কোনো নতুন নিয়ম নেই। ফাংশন নিজেকে ডাকলেও ঠিক একই ঘটনা ঘটে: প্রতিটি ডাক পায় নিজের আলাদা frame, নিজের আলাদা n.

এ কারণেই fact(4)-এর n আর fact(3)-এর n একে অপরকে নষ্ট করে না — নাম এক হলেও তারা আলাদা ঘরে থাকে, যেমন লাইনের প্রত্যেক মানুষের মাথায় নিজের আলাদা হিসাব। নিচের debugger সিমুলেটরে ডান পাশের stack খেয়াল করুন — প্রথমে উঁচু হবে, তারপর এক এক করে নামবে:

1#include <stdio.h>23int fact(int n) {4    if (n <= 1)5        return 1;            // base case6    return n * fact(n - 1);  // recursive case7}89int main(void) {10    printf("%d\n", fact(4));11    return 0;12}

Call stack (ওপরে = সবশেষে ডাকা)

fact(1)
fact(2)
fact(3)
fact(4)
main
fact-এর frame

main ডাকল fact(4). stack-এ main-এর ওপর তৈরি হলো fact(4)-এর frame, তাতে n = 4. main অপেক্ষা করছে — উত্তর না পেলে printf চলবে না।
fact(4) নিজেকে ডাকল। 4 ≤ 1 নয়, তাই লাইন ৬ চলছে: 4 × fact(3). গুণটা এখনো করা যাচ্ছে না — fact(3)-এর উত্তর লাগবে। fact(4) তার অসমাপ্ত হিসাব “4 × ?” নিয়ে অপেক্ষায় রইল, আর ওপরে তৈরি হলো fact(3)-এর নতুন frame.
আরও এক তলা। fact(3) একই কাজ করল: “3 × ?” রেখে ডাকল fact(2). খেয়াল করুন, তিনটি frame-এ তিনটি আলাদা n — 4, 3, 2.
stack সবচেয়ে উঁচু। fact(2) ডাকল fact(1). এখন fact-এর ৪টি frame একসাথে মেমরিতে। fact(100) হলে থাকত ১০০টি — রিকার্শনের মেমরি খরচ এখানেই।
Base case! fact(1)-এ শর্ত n <= 1 সত্য। আর কাউকে ডাকতে হলো না — সোজা 1 ফেরত। এখান থেকে stack নামতে শুরু করবে।
প্রথম অসমাপ্ত হিসাব শেষ। fact(1)-এর frame মুছে গেল। fact(2) এতক্ষণ “2 × ?” নিয়ে অপেক্ষায় ছিল — এবার ? = 1, তাই 2 ফেরত দিল।
আরও এক তলা নিচে। fact(3) পেল 2, হিসাব করল 3 × 2 = 6, ফেরত দিল। যে ক্রমে frame তৈরি হয়েছিল, ঠিক তার উল্টো ক্রমে মুছে যাচ্ছে — সবশেষে আসা, সবার আগে বিদায়।
উত্তর main-এর হাতে। fact(4) হিসাব করল 4 × 6 = 24. main উত্তর পেয়ে ছাপল 24. পুরো ঘটনায় গুণগুলো হয়েছে ফেরার পথে, যাওয়ার পথে শুধু অসমাপ্ত হিসাব জমেছে।

এই ওঠা-নামা নিজের চোখে দেখতে নিচের প্রোগ্রামটি চালান। প্রতিটি ডাক কত গভীরে, তা বোঝাতে লেখা ডানে সরে যাবে — ঢোকার সময় একবার, বের হওয়ার সময় আরেকবার ছাপা হবে:

#include <stdio.h>

int fact(int n, int depth) {
    printf("%*scall fact(%d)\n", depth * 2, "", n);
    if (n <= 1) {                                    /* base case */
        printf("%*sbase case -> 1\n", depth * 2, "");
        return 1;
    }
    int result = n * fact(n - 1, depth + 1);        /* recursive case */
    printf("%*sfact(%d) returns %d\n", depth * 2, "", n, result);
    return result;
}

int main(void) {
    printf("answer = %d\n", fact(4, 0));
    return 0;
}

depth শুধু ছাপার জন্য — প্রতিটি নতুন ডাকে ১ বাড়ে, আর %*s সেই অনুপাতে ফাঁকা জায়গা বসায়। আউটপুটে দেখবেন একটি “V” আকৃতি: চারটি call ক্রমশ ডানে সরে যায় (stack উঠছে), তারপর returns লাইনগুলো ক্রমশ বাঁয়ে ফেরে (stack নামছে)। লক্ষ করুন, result হিসাবের লাইনটি নিজেকে ডাকার পরে — তাই সব গুণ হয় ফেরার পথে, আর returns ছাপা হয় উল্টো ক্রমে: আগে fact(2), শেষে fact(4).

৪ · Stack overflow — যখন নামা আর থামে না

Call stack অসীম নয়। প্রোগ্রাম শুরুর সময় অপারেটিং সিস্টেম এর জন্য একটি নির্দিষ্ট মাপের জায়গা দেয় — Linux-এ সাধারণত ৮ MB, Windows-এ সাধারণত ১ MB. প্রতিটি frame সেখান থেকে কিছু জায়গা নেয়। ডাক যদি থামতেই না চায়, একসময় জায়গা ফুরিয়ে যায়। একে বলে stack overflow, আর প্রোগ্রাম তখন সাথে সাথে crash করে।

দুইভাবে এটি ঘটে:

🪞 Base case নেই বা পৌঁছানো যায় না

মুখোমুখি আয়নার মতো অন্তহীন ডাক। base case ভুলে গেলে, অথবা ২ করে কমিয়ে বিজোড় সংখ্যা থেকে শূন্য টপকে গেলে — যত বড় stack-ই থাকুক, ভরে যাবেই।

যেকোনো ইনপুটেই crash

📏 ইনপুট খুব বড়

ফাংশন পুরোপুরি ঠিক, কিন্তু গভীরতা বিশাল। ১ থেকে ১০ লাখ পর্যন্ত যোগফল রিকার্শনে বের করতে গেলে একসাথে ১০ লাখ frame লাগবে। ছোট ইনপুটে পরীক্ষায় পাস, আসল ডেটায় crash.

শুধু বড় ইনপুটে crash

Linux-এ stack overflow সাধারণত এভাবে দেখা দেয় — কোনো ব্যাখ্যা ছাড়াই:

$ ./sum_recursive
Segmentation fault (core dumped)

Windows-এ প্রোগ্রাম চুপচাপ বন্ধ হয়ে যেতে পারে, আর exit code হিসেবে আসে 0xC00000FD — যার মানে STATUS_STACK_OVERFLOW. এটা চিনে রাখুন। দ্বিতীয় ধরনটি বেশি বিপজ্জনক, কারণ ক্লাসের ছোট উদাহরণে কিছুই ধরা পড়ে না।

প্রোগ্রামারদের সবচেয়ে জনপ্রিয় প্রশ্নোত্তর ওয়েবসাইটটির নামও “Stack Overflow” — এই error-এর নামেই রাখা। ডাকের গভীরতা কম রাখার একটি সহজ নিয়ম: প্রতিটি ডাকে সমস্যা যদি অর্ধেক হয় (যেমন binary search), তাহলে ১০ লাখ উপাদানেও গভীরতা মাত্র ২০-এর মতো। আর যদি প্রতিবার মাত্র ১ কমে, গভীরতা হবে ১০ লাখ। প্রথমটি নিরাপদ, দ্বিতীয়টিতে লুপই ভালো।

পর্ব ০২-এর “১ থেকে ১০০-এর খেলা” মনে আছে? প্রতিবার মাঝের সংখ্যাটি বলে অর্ধেক বাদ দেওয়া। সেটিও আসলে রিকার্শন: “পুরো তালিকায় খোঁজো” মানে “মাঝখানে দেখো; না মিললে বাঁ বা ডান অর্ধেকে একইভাবে খোঁজো।” খোঁজার জায়গা খালি হয়ে গেলে, অথবা মিলে গেলে — base case. Recursive binary search তাই রিকার্শনের একটি নিরাপদ, সুন্দর উদাহরণ।

৫ · Fibonacci — একই কাজ বারবার করার দাম

Fibonacci ধারা: 0, 1, 1, 2, 3, 5, 8, 13, 21 … প্রথম দুটি 0 আর 1, তারপর প্রতিটি সংখ্যা আগের দুটির যোগফল। সংজ্ঞাটি দেখতে নিখুঁত রিকার্শন:

fib(0) = 0, fib(1) = 1 (দুটি base case)
fib(n) = fib(n − 1) + fib(n − 2) (দুটি ছোট ডাক)

এই ধারার নাম এসেছে ইতালির গণিতবিদ Leonardo of Pisa-র ডাকনাম Fibonacci থেকে। ১২০২ সালে লেখা তাঁর বই Liber Abaci-তে খরগোশের বংশবৃদ্ধির একটি হিসাবের ধাঁধায় ধারাটি আসে। একই বই ইউরোপে আমাদের পরিচিত ০–৯ অঙ্কপদ্ধতি ছড়াতেও বড় ভূমিকা রাখে। তবে ধারাটি এর বহু আগে ভারতীয় ছন্দশাস্ত্রেও পরিচিত ছিল।

সমস্যাটা হলো, এখানে প্রতিটি ডাক নিজে থেকে দুটি নতুন ডাক তৈরি করে। কে কাকে ডাকল, সেটা গাছের মতো আঁকলে পাওয়া যায় একটি call tree. fib(5)-এর গাছটি তলা ধরে ধরে দেখুন, আর গুনতে থাকুন:

fib(5)

fib(4)

fib(3)

fib(2)

fib(1)

fib(2)

fib(1)

fib(0)

fib(1)

fib(0)

fib(1)

fib(0)

fib_memo(5)নিচে নামার পথ — প্রথমবার সব হিসাব

fib(5) → fib(4) → fib(3) → fib(2) → fib(1), fib(0)
fib(2) = 1 + 0 = 1  → টেবিলে লেখা হলো memo[2] = 1

fib_memo(5)ফেরার পথে — টেবিল কাজে লাগছে

fib(3) = memo[2] + fib(1) = 1 + 1 = 2   → memo[3]
fib(4) = fib(3) + fib(2) → টেবিলে আছে: 1   → memo[4] = 3

fib_memo(5)শেষ ধাপ

fib(5) = fib(4) + fib(3) → টেবিলে আছে: 2 = 3 + 2 = 5
মোট ডাক: ৯টি (আগে ছিল ১৫টি)

হিসাব

এ পর্যন্ত মোট ডাক
memo[2]
memo[3]
memo[4]
memo[5]

গাছের মূল। আমরা fib(5) চাইলাম। এটি নিজে উত্তর জানে না, তাই দুটি ছোট ডাক দেবে। মোট ডাক এখন ১টি।
প্রথম তলা। fib(5) ডাকল fib(4) আর fib(3). মোট ৩টি ডাক।
দ্বিতীয় তলা। প্রত্যেকে আবার দুটি করে ডাকল। দেখুন — fib(3) আবার এসেছে! একবার এসেছিল প্রথম তলায়, এখন fib(4)-এর ভেতর থেকে আবার। সবুজগুলো base case — ওরা আর কাউকে ডাকে না। মোট ৭টি।
তৃতীয় তলা। গাছ আরও চওড়া হলো — মোট ১৩টি ডাক। fib(2) তৃতীয়বারের মতো হাজির।
শেষ তলা। সবশেষে আরও দুটি base case. fib(5) = 5 বের করতে মোট ডাক লাগল ১৫টি। কিন্তু আলাদা প্রশ্ন ছিল মাত্র ৬টি: fib(0) থেকে fib(5).
অপচয় চিনুন। লাল দাগের ঘরগুলো একই কাজের পুনরাবৃত্তি: fib(3) হিসাব হয়েছে ২ বার, fib(2) ৩ বার; আর fib(1) এসেছে ৫ বার, fib(0) ৩ বার। n বাড়লে এই অপচয় গুণে গুণে বাড়ে — প্রায় পুরো সময় যায় একই উত্তর বারবার বের করতে।
সমাধান: উত্তর লিখে রাখুন। এবার একটি টেবিল (memo) রাখলাম। নিচে নামার পথে fib(2) প্রথমবার হিসাব হলো = 1, লিখে রাখা হলো memo[2]-এ। এ পর্যন্ত ৬টি ডাক।
টেবিল কাজে লাগছে। ফেরার পথে fib(3) = 2 হিসাব হয়ে টেবিলে উঠল। এরপর fib(4)-এর দরকার হলো fib(2) — কিন্তু এবার নতুন করে হিসাব নয়, টেবিল থেকে সরাসরি 1 নেওয়া হলো। memo[4] = 3.
১৫ থেকে ৯। fib(5)-এর দরকার fib(3) — টেবিলে আছে 2. উত্তর 3 + 2 = 5, মোট ডাক মাত্র ৯টি। প্রতিটি fib(k) একবারই হিসাব হয়েছে। n = 5-এ পার্থক্য ছোট, কিন্তু n = 30-এ এটি ২৭ লাখ বনাম ৫৯ — নিচের কোডে নিজেই দেখুন।

একবার হিসাব করা উত্তর টেবিলে লিখে রাখা, আর পরে একই প্রশ্ন এলে টেবিল থেকে দেওয়া — এই কৌশলের নাম memoization (মেমোয়াইজেশন; “memo” মানে ছোট্ট চিরকুট)। পরীক্ষার হলে একটি অঙ্কের মাঝের ফল খাতার কোণে লিখে রাখলে যেমন পরের প্রশ্নে আবার কষতে হয় না — ঠিক তেমন। নিচের কোডে দুটি ভার্সনই একসাথে মাপা হচ্ছে:

#include <stdio.h>
long long calls = 0, memo[50];           /* memo[n] == 0 : not known yet */

long long fib(int n) {
    calls++;
    if (n <= 1) return n;                          /* base cases */
    return fib(n - 1) + fib(n - 2);                /* two smaller copies */
}
long long fib_memo(int n) {
    calls++;
    if (n <= 1) return n;
    if (memo[n] == 0) memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];                                /* known: just reuse */
}
int main(void) {
    long long a = fib(30);       printf("naive: fib(30) = %lld, calls = %lld\n", a, calls);
    calls = 0;
    long long b = fib_memo(30);  printf("memo : fib(30) = %lld, calls = %lld\n", b, calls);
    return 0;
}

দুই লাইনেই উত্তর এক — 832040. কিন্তু সরল ভার্সনে ডাক হয় ২৬,৯২,৫৩৭টি, আর memo ভার্সনে মাত্র ৫৯টি। প্রথম ভার্সনের ডাকের সংখ্যা ঠিক 2 × fib(31) − 1, অর্থাৎ উত্তরের প্রায় ৩ গুণ — উত্তর যত দ্রুত বাড়ে, ডাকও তত দ্রুত বাড়ে। n এক বাড়লে ডাক বাড়ে প্রায় ১.৬১৮ গুণ — এমন বৃদ্ধিকে বলে exponential. fib(40)-এ ডাক লাগবে ৩৩ কোটির বেশি। একটি লক্ষ করার বিষয়: a আর b আলাদা লাইনে আগে হিসাব করা হয়েছে, কারণ একই printf-এর ভেতরে fib(30) আর calls দিলে C কোনটি আগে হিসাব করবে, তার নিশ্চয়তা দেয় না।

মূল ধারণা

রিকার্শন নিজে ধীর নয় — ধীর হয় যখন একই উপ-সমস্যা বারবার সমাধান হয়। call tree আঁকলেই এটা ধরা পড়ে। যেখানে উপ-সমস্যা বারবার ফিরে আসে, সেখানে উত্তর জমিয়ে রাখার কৌশলটিকে বড় পরিসরে বলে dynamic programming — পর্ব ৪২-এ এর পুরো রূপ দেখবেন। আজকের memo টেবিলটিই তার প্রথম ধাপ।

৬ · Tower of Hanoi — যেখানে রিকার্শনই সবচেয়ে সহজ পথ

এতক্ষণের উদাহরণগুলো লুপ দিয়েও সহজে করা যায়। এবার এমন একটি সমস্যা দেখুন, যেটি রিকার্শনে ভাবলে কয়েক লাইনের, আর অন্যভাবে ভাবলে মাথা ঘুরিয়ে দেয়।

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

ফরাসি গণিতবিদ Édouard Lucas ১৮৮৩ সালে ধাঁধাটি প্রকাশ করেন, সাথে জুড়ে দেন একটি কাল্পনিক কিংবদন্তি: এক মন্দিরে পুরোহিতেরা ৬৪টি সোনার চাকতি সরাচ্ছেন, কাজ শেষ হলে নাকি পৃথিবী ধ্বংস হবে। ভয়ের কিছু নেই — ৬৪টি চাকতিতে চাল লাগে 2⁶⁴ − 1, প্রায় ১.৮ × ১০^১৯টি। সেকেন্ডে একটি করে চাল দিলে লাগবে প্রায় ৫৮,০০০ কোটি বছর — মহাবিশ্বের বর্তমান বয়সের প্রায় ৪০ গুণ।

রিকার্শনে ভাবলে সমাধান তিন লাইনে: n টি চাকতি A থেকে C-তে নিতে হলে — (১) ওপরের n − 1টি চাকতি A থেকে B-তে সরিয়ে রাখুন (C-কে সাহায্য হিসেবে ব্যবহার করে); (২) সবচেয়ে বড় চাকতিটি A থেকে C-তে নিন; (৩) B-তে রাখা n − 1টি চাকতি C-তে, বড়টির ওপরে আনুন। ধাপ (১) আর (৩) হুবহু একই ধাঁধা, শুধু একটি চাকতি কম — আর ০টি চাকতি হলে কিছুই করার নেই, সেটাই base case.

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;                          // base case: কিছু সরানোর নেই
    hanoi(n - 1, from, via, to);                 // ১) ওপরের n-1টি পাশে সরাও
    printf("Move disc %d: %c -> %c\n", n, from, to);   // ২) বড়টি গন্তব্যে
    hanoi(n - 1, via, to, from);                 // ৩) n-1টি বড়টির ওপরে আনো
}

hanoi(3, 'A', 'C', 'B') ডাকলে কী ঘটে, প্রতিটি চালের পর খুঁটিগুলোর অবস্থা দেখুন। চাকতির নম্বর দেওয়া আছে আকার অনুযায়ী — ১ সবচেয়ে ছোট, ৩ সবচেয়ে বড়; প্রতিটি খুঁটিতে বাঁ থেকে ডানে লেখা মানে নিচ থেকে ওপরে:

তিন খুঁটির অবস্থা (নিচ → ওপর)

খুঁটি A
খুঁটি B
খুঁটি C
মোট চাল

শুরুর অবস্থা। তিনটি চাকতিই A-তে। hanoi(3, A, C, B) প্রথমেই নিজেকে ডাকবে hanoi(2, A, B, C) — অর্থাৎ “ওপরের দুটিকে আগে B-তে সরাও।” এই উপ-কাজটি চলবে চাল ১ থেকে ৩ পর্যন্ত।
চাল ১: চাকতি ১, A → C. দুটি চাকতি B-তে নিতে হলে আগে ছোটটিকে পথ থেকে সরাতে হবে — সেটি গেল C-তে। এটি সবচেয়ে গভীর ডাক hanoi(1, A, C, B)-এর কাজ।
চাল ২: চাকতি ২, A → B. মাঝারি চাকতি এখন খোলা, সেটি তার গন্তব্য B-তে গেল।
চাল ৩: চাকতি ১, C → B. ছোটটি মাঝারিটির ওপরে বসল। প্রথম উপ-কাজ শেষ: ওপরের দুটি চাকতি এখন B-তে, আর A-তে শুধু সবচেয়ে বড়টি।
চাল ৪: চাকতি ৩, A → C. এই মুহূর্তের জন্যই এত আয়োজন! বড় চাকতি সরাসরি C-তে। এখন বাকি কাজ: B-এর দুটি চাকতি C-তে আনা — আবার সেই একই ছোট ধাঁধা, hanoi(2, B, C, A).
চাল ৫: চাকতি ১, B → A. মাঝারিটিকে মুক্ত করতে ছোটটি সরল A-তে। লক্ষ করুন, চাল ১-এর মতোই আচরণ — শুধু খুঁটিগুলোর ভূমিকা বদলেছে।
চাল ৬: চাকতি ২, B → C. মাঝারিটি বড়টির ওপরে বসল।
চাল ৭: চাকতি ১, A → C. শেষ! মোট চাল ৭ = 2³ − 1. ৪টি চাকতিতে লাগে ২ × ৭ + ১ = ১৫টি, ৫টিতে ৩১টি — প্রতিটি নতুন চাকতি চালের সংখ্যা প্রায় দ্বিগুণ করে। এখানে কোনো অপচয় নেই, এর চেয়ে কম চালে সম্ভবই নয়।

খেয়াল করুন, কোডে কোথাও “এখন ছোটটা কোথায় যাবে” — এই হিসাব নেই। রিকার্শন সেই জটিলতা নিজেই সামলেছে। এই ধরনের কৌশল — বড় সমস্যাকে ছোট টুকরোয় ভাগ, প্রতিটি আলাদা সমাধান, তারপর জোড়া — এর নাম divide and conquer. Merge sort, quick sort, binary search সবাই এই পরিবারের; পর্ব ৪০ ও ৪১-এ এদের বিস্তারিত দেখবেন।

৭ · রিকার্শন নাকি লুপ — কখন কোনটি

যা কিছু রিকার্শনে করা যায়, তা লুপ দিয়েও করা যায় (দরকার হলে নিজের হাতে একটি stack বানিয়ে) — আর উল্টোটাও সত্য। তাই প্রশ্ন “কোনটি পারে” নয়, প্রশ্ন “কোনটিতে সমাধান পরিষ্কার ও নিরাপদ।” লুপ দিয়ে বারবার কাজ করার পদ্ধতিকে বলে iteration.

পরিস্থিতি	ভালো পছন্দ	কেন
১ থেকে n পর্যন্ত যোগ, factorial, তালিকা একবার ঘোরা	লুপ	সরল এক সারি কাজ। রিকার্শনে বাড়তি frame খরচ আর stack overflow-এর ঝুঁকি, লাভ নেই।
ফোল্ডারের ভেতর ফোল্ডার, তার ভেতর আরও ফোল্ডার	রিকার্শন	ডেটার গঠনটাই নিজের ভেতরে নিজে। “এই ফোল্ডারের মাপ = ফাইলগুলোর মাপ + প্রতিটি সাব-ফোল্ডারের মাপ।”
Tree (পর্ব ৩৫), JSON বা HTML-এর মতো নেস্টেড ডেটা	রিকার্শন	প্রতিটি শাখা নিজেই একটি ছোট গাছ। গভীরতা সাধারণত কম।
Divide and conquer (binary search, merge sort, Hanoi)	রিকার্শন	প্রতি ধাপে সমস্যা অর্ধেক — গভীরতা কম, কোড ছোট ও প্রমাণযোগ্য।
লাখ লাখ উপাদানের লম্বা শিকল (linked list ঘোরা)	লুপ	প্রতি ধাপে মাত্র ১ কমে — গভীরতা = উপাদানের সংখ্যা, stack overflow প্রায় নিশ্চিত।
একই উপ-সমস্যা বারবার আসে (Fibonacci)	memo সহ রিকার্শন, অথবা লুপ	সরল রিকার্শন exponential. লুপে শুধু আগের দুটি সংখ্যা মনে রাখলেই চলে।

Tail call — যে রিকার্শন লুপ হয়ে যেতে পারে

fact-এর return n * fact(n - 1); লাইনে নিজেকে ডাকার পরে গুণ বাকি থাকে — তাই প্রতিটি frame উত্তরের অপেক্ষায় টিকে থাকতে বাধ্য। কিন্তু যদি এমনভাবে লেখা যায় যে নিজেকে ডাকাটাই একদম শেষ কাজ, পরে আর কিছু করার নেই? তখন আগের frame রেখে দেওয়ার কোনো কারণ থাকে না। এমন ডাককে বলে tail call:

long fact_acc(int n, long acc) {            // acc = এ পর্যন্ত গুণফল
    if (n <= 1) return acc;
    return fact_acc(n - 1, acc * n);         // ডাকটাই শেষ কাজ: tail call
}
// ব্যবহার: fact_acc(5, 1) → 120

এখানে গুণ হয়ে যাচ্ছে যাওয়ার পথেই, acc-এর ভেতরে। GCC বা Clang-এ -O2 দিয়ে compile করলে compiler প্রায়ই এই ডাককে চুপচাপ একটি লুপে বদলে দেয় — frame আর জমে না।

কিন্তু সাবধান: C ভাষার নিয়ম এই রূপান্তরের কোনো নিশ্চয়তা দেয় না। এটি compiler-এর ইচ্ছাধীন একটি optimization. -O0 দিয়ে debug build করলে, বা কোডে সামান্য পরিবর্তন হলে, একই ফাংশন আবার stack ভরিয়ে crash করতে পারে। তাই বিশাল গভীরতার কাজে “compiler সামলে নেবে” ভরসায় রিকার্শন লিখবেন না — সরাসরি লুপ লিখুন।

৮ · AI-এর যুগে রিকার্শন যাচাই

AI রিকার্শন লিখতে খুব পছন্দ করে — কোড ছোট আর দেখতে মার্জিত হয়। সমস্যা হলো, রিকার্শনের ভুলগুলো ছোট ইনপুটে প্রায় কখনো ধরা পড়ে না। fib(10) বা ১০০টি উপাদানে সব ঠিক; আসল ডেটায় প্রোগ্রাম হয় ঘণ্টার পর ঘণ্টা চলে, নয়তো crash করে।

AI-এর রিকার্শনে যেসব ভুল প্রায়ই দেখা যায়

AI-এর ভুল	আপনি যা দেখবেন	কীভাবে ধরবেন
base case শুধু `n == 1`, কিন্তু 0 বা ঋণাত্মক ইনপুট ভাবেনি	n = 0 দিলে crash (`Segmentation fault`)	edge case-এ চালান: 0, −1, 1
base case আছে, কিন্তু ২ করে কমায় বা ভুল দিকে যায়	কিছু ইনপুটে চলে, কিছুতে অন্তহীন	তৃতীয় প্রশ্ন: প্রতিটি ইনপুট কি base case-এ পৌঁছায়?
সরল Fibonacci-র মতো একই উপ-সমস্যা বারবার	n = 45-এ প্রোগ্রাম যেন আটকে গেছে	call tree আঁকুন, একটি ডাক-গণনাকারী বসান
লাখ লাখ উপাদানে প্রতি ধাপে ১ কমানো রিকার্শন	ছোট টেস্টে পাস, আসল ডেটায় crash	সর্বোচ্চ গভীরতা কত হবে, হিসাব করুন
নিজেকে ডেকেছে, কিন্তু ফল `return` করতে ভুলেছে	ভুল বা আবর্জনা উত্তর; warning `control reaches end of non-void function`	`-Wall -Wextra` দিয়ে compile

AI-কে রিকার্শন লিখতে বললে শুধু “লিখে দাও” নয় — যাচাইয়ের তথ্যও সাথে চেয়ে নিন। নিচের কাঠামোটি কপি করে ব্যবহার করুন:

C-তে একটি recursive ফাংশন লিখে দাও যা [এখানে কাজটি লিখুন]. ইনপুট সর্বোচ্চ [যেমন ১০ লাখ] পর্যন্ত হতে পারে। কোডের সাথে এগুলো আলাদা করে বলো: ১. base case কোনটি, আর প্রতিটি সম্ভাব্য ইনপুট (০, ঋণাত্মক, খুব বড়) কীভাবে সেখানে পৌঁছায়। ২. সর্বোচ্চ ইনপুটে রিকার্শন কত গভীরে যাবে — stack overflow-এর ঝুঁকি আছে কি না। ৩. মোট কতবার ফাংশন ডাকা হবে (time complexity), কোনো উপ-সমস্যা বারবার হিসাব হচ্ছে কি না। ৪. একই কাজের একটি লুপ-ভিত্তিক (iterative) সমাধানও দাও, আর বলো কোনটি কোন পরিস্থিতিতে ভালো।

AI-এর রিকার্শন হাতে পেলে — যাচাইয়ের চেকলিস্ট

base case খুঁজে পেয়েছি, এবং প্রতিটি ইনপুট — ০, ঋণাত্মক, বিজোড়-জোড় — সেখানে পৌঁছায়
প্রতিটি ডাকে সমস্যা নিশ্চিতভাবে ছোট হচ্ছে, কোনো পথে একই আকারে আবার ডাক যাচ্ছে না
সবচেয়ে বড় সম্ভাব্য ইনপুটে গভীরতা কত, হিসাব করেছি — লাখের ঘরে গেলে লুপ চেয়েছি
ছোট একটি ইনপুটের call tree কাগজে এঁকেছি — একই ডাক বারবার এলে memo বা লুপ চেয়েছি
-Wall -Wextra দিয়ে compile করে শূন্য warning, আর অন্তত একটি ফল হাতে হিসাব করে মিলিয়েছি

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন। এগুলোই আপনাকে কোড-লেখক থেকে সিস্টেম-চিন্তক বানাবে।

প্র ০১রিকার্শন কি লুপের চেয়ে ধীর? যদি হয়, ঠিক কোথায় সময় আর মেমরি খরচ হয়?

একই অ্যালগরিদম হলে সাধারণত হ্যাঁ, একটু ধীর — আর মেমরিতে অনেক বেশি খরুচে। কারণটা ফাংশন ডাকার খরচে লুকিয়ে আছে।

প্রতিটি ডাকের নিজস্ব খরচ: নতুন frame তৈরি, প্যারামিটার বসানো, ফেরার ঠিকানা রাখা, কিছু register সংরক্ষণ, তারপর ফেরার সময় সব গুছিয়ে আগের জায়গায় যাওয়া। লুপের একটি ঘোরায় এসবের কিছুই লাগে না — শুধু একটি শর্ত যাচাই আর আগের জায়গায় লাফ।
মেমরি: ১ থেকে n যোগের লুপে লাগে হাতে গোনা কয়েকটি ভ্যারিয়েবল, n যত বড়ই হোক। রিকার্শনে একসাথে n-টি frame — মেমরি খরচ n-এর সমানুপাতে বাড়ে, আর stack-এর সীমা ছাড়ালে crash.
Cache-এর প্রভাব: বিশাল গভীরতায় stack-এর বড় অংশ জুড়ে ডেটা ছড়িয়ে পড়ে, যা CPU-র দ্রুত মেমরিতে (cache) সবসময় ধরে না।

তবে গল্পের অন্য দিকও আছে। আধুনিক compiler ছোট ফাংশন inline করে দেয়, tail call-কে লুপে বদলায় — অনেক সময় পার্থক্য প্রায় শূন্য হয়ে যায়। আর আসল বড় পার্থক্য প্রায়ই আসে অ্যালগরিদম থেকে, রিকার্শন থেকে নয়। সরল Fibonacci ধীর রিকার্শনের জন্য নয়, একই কাজ লক্ষ লক্ষ বার করার জন্য; memo দিলে রিকার্শন রেখেই সেটি বিদ্যুৎগতির। অন্যদিকে tree ঘোরার মতো কাজে লুপ দিয়ে লিখতে গেলে নিজের হাতে একটি stack বানাতে হয় — তাতে কোড দীর্ঘ ও ভুলপ্রবণ হয়, গতিতে লাভ সামান্য।

কিছু ভাষা এজন্য সীমা বেঁধে দেয় — যেমন Python-এ ডিফল্টভাবে রিকার্শনের গভীরতা প্রায় ১০০০-এ আটকে যায়, যাতে stack overflow-এ পুরো প্রোগ্রাম ভেঙে না পড়ে, বরং একটি পরিষ্কার error আসে।

মূল উপলব্ধি: প্রশ্নটা “রিকার্শন খারাপ কি না” নয়। প্রশ্ন হলো — সমস্যার গঠন কি নিজেই recursive, গভীরতা কি নিয়ন্ত্রণে, আর কোনো কাজ কি বারবার হচ্ছে? এই তিনটির উত্তরেই সিদ্ধান্ত।

প্র ০২কিছু ভাষা tail call-কে লুপে বদলানোর নিশ্চয়তা দেয়, C কেন দেয় না?

Scheme-এর মতো কিছু functional ভাষায় লুপ বলতে গেলে নেই — সব বারবার করার কাজই রিকার্শনে লেখা হয়। সেখানে tail call লুপে বদলানো ঐচ্ছিক সুবিধা হলে চলত না; না হলে সাধারণ একটি “লুপ” লাখবার ঘুরলেই stack ভরে যেত। তাই Scheme-এর মানদণ্ডে এটি বাধ্যতামূলক — tail call মানেই নতুন frame নয়।

C-র অবস্থান আলাদা, কয়েকটি বাস্তব কারণে:

C-তে লুপ আছে। যার লুপ দরকার, সে for বা while লিখবে। ভাষাকে বাড়তি শর্তে বাঁধার দরকার পড়েনি।
লোকাল ভ্যারিয়েবলের ঠিকানা: C-তে একটি লোকাল ভ্যারিয়েবলের ঠিকানা (পর্ব ১৭-এ আসবে pointer) অন্য ফাংশনে পাঠানো যায়। যদি ডাকা ফাংশন সেই ঠিকানা ব্যবহার করে, আগের frame মুছে ফেলা যায় না — তখন রূপান্তরই অসম্ভব। compiler-কে প্রতিবার এটা যাচাই করতে হয়।
Debugging: frame মুছে গেলে crash-এর সময় কোন ফাংশন কাকে ডেকেছিল, সেই ইতিহাস (stack trace) হারিয়ে যায়। C প্রোগ্রামাররা debug build-এ সেটি চান।
নানা হার্ডওয়্যার: C চলে ছোট microcontroller থেকে supercomputer পর্যন্ত। প্রতিটি প্ল্যাটফর্মে ফাংশন ডাকার নিয়ম ভিন্ন, সব জায়গায় এই রূপান্তর সমান সহজ নয়।

ফল হলো: GCC ও Clang -O2-এ সুযোগ পেলেই রূপান্তর করে, কিন্তু প্রতিশ্রুতি দেয় না। Clang নিজস্ব একটি বিশেষ নির্দেশ (attribute) যোগ করেছে, যা দিয়ে প্রোগ্রামার জোর দিয়ে বলতে পারেন “এটা tail call হতেই হবে, না হলে compile error দাও” — কিন্তু সেটি মানদণ্ডের অংশ নয়, সব compiler-এ চলে না।

মূল উপলব্ধি: একটি ভাষার নিয়ম তার ব্যবহারকারীদের প্রয়োজন থেকে জন্মায়। Scheme-এর কাছে tail call অস্তিত্বের প্রশ্ন, C-র কাছে একটি ঐচ্ছিক গতি-বৃদ্ধি। “compiler সাধারণত করে” আর “ভাষা নিশ্চয়তা দেয়” — এ দুটির পার্থক্য বোঝা পেশাদার প্রোগ্রামারের লক্ষণ।

প্র ০৩রিকার্শন আর mathematical induction কি আসলে একই চিন্তা? তাহলে এটা দিয়ে কোড সঠিক প্রমাণ করা যায় কীভাবে?

হ্যাঁ — এরা একই মুদ্রার দুই পিঠ। Induction প্রমাণ করে, রিকার্শন হিসাব করে, কিন্তু কাঠামো হুবহু এক।

Induction-এর ভিত্তি (base): কথাটি সবচেয়ে ছোট মানের জন্য সত্য। ↔ base case: সবচেয়ে ছোট ইনপুটে ফাংশন সরাসরি ঠিক উত্তর দেয়।
Induction-এর ধাপ: k-এর জন্য সত্য হলে k + 1-এর জন্যও সত্য। ↔ recursive case: ছোট ডাক ঠিক উত্তর দিলে বড়টিও ঠিক উত্তর বানায়।

উদাহরণ — Tower of Hanoi সঠিক, তা প্রমাণ করি। ০টি চাকতিতে কিছু না করাই ঠিক (ভিত্তি)। ধরে নিই n − 1টি চাকতি সঠিকভাবে সরানো যায় (ধাপের অনুমান)। তাহলে n টির জন্য: ওপরের n − 1টি B-তে সরানো বৈধ — কারণ নিচের বড় চাকতিটি তাদের সবার চেয়ে বড়, কোনো নিয়ম ভাঙে না। বড়টি C-তে যাওয়া বৈধ — C তখন খালি। তারপর n − 1টি C-তে বড়টির ওপর আনা বৈধ। প্রমাণ শেষ। একই সাথে চালের সংখ্যাও বেরিয়ে আসে: T(n) = 2·T(n − 1) + 1, যার সমাধান 2ⁿ − 1.

এই চিন্তা শুধু পরীক্ষার খাতায় নয়। বিমান চলাচল বা চিকিৎসা-যন্ত্রের মতো জায়গায় যেখানে ভুলের সুযোগ নেই, সেখানে প্রোগ্রাম সঠিক কি না তা গাণিতিকভাবে প্রমাণ করার টুল ব্যবহার হয় — আর রিকার্শনের ক্ষেত্রে তাদের মূল অস্ত্র ঠিক এই induction. পর্ব ০২-এর loop invariant-ও একই যুক্তির লুপ-রূপ।

আর ব্যবহারিক লাভ: যখন আপনি recursive ফাংশন লিখতে গিয়ে পুরো ডাকাডাকি মাথায় চালানোর চেষ্টা ছেড়ে দিয়ে শুধু বলেন “ছোট ডাকটি ঠিক উত্তর দেবে ধরে নিচ্ছি” — সেটা অলস ভাবনা নয়, সেটাই induction-এর অনুমান। এই “বিশ্বাসের লাফ” গণিত দিয়ে সমর্থিত।

মূল উপলব্ধি: ভালো recursive কোড লেখা মানে একটি ছোট induction প্রমাণ লেখা। base case আর “ছোট হওয়া” ঠিক থাকলে, পুরো ফাংশন ঠিক — আলাদা করে প্রতিটি ইনপুট পরীক্ষার দরকার নেই।

প্র ০৪সরল Fibonacci-তে n মাত্র ১০ বাড়ালে সময় কেন প্রায় ১২৩ গুণ হয়ে যায়?

সরল fib(n)-এ মোট ডাকের সংখ্যা গুনে দেখা যায়: C(n) = C(n − 1) + C(n − 2) + 1 — অর্থাৎ ডাকের সংখ্যাও নিজেই একটি Fibonacci-র মতো ধারা! সঠিক হিসাবে C(n) = 2 × fib(n + 1) − 1. fib(5)-এ ১৫, fib(30)-এ ২৬,৯২,৫৩৭, fib(40)-এ ৩৩,১১,৬০,২৮১ — ৩৩ কোটির বেশি।

Fibonacci ধারায় পাশাপাশি দুটি সংখ্যার অনুপাত দ্রুত একটি নির্দিষ্ট মানের কাছে চলে যায় — প্রায় ১.৬১৮, যার নাম golden ratio. তাই n এক বাড়লে ডাক বাড়ে প্রায় ১.৬১৮ গুণ, আর n দশ বাড়লে ১.৬১৮^১০ ≈ ১২৩ গুণ। (fib(30) থেকে fib(40)-এ ডাক সত্যিই প্রায় ১২৩ গুণ।) এমন বৃদ্ধিকে বলে exponential — প্রতিটি ধাপে গুণ, যোগ নয়।

অনুভব করার জন্য: ধরুন আপনার কম্পিউটার সেকেন্ডে দশ কোটি ডাক সামলায়। fib(40) লাগবে কয়েক সেকেন্ড, fib(50)-এ ডাক প্রায় ৪ হাজার কোটি — কয়েক মিনিট। fib(80)-এ প্রায় দুই যুগ, আর fib(90)-এ হাজার বছরেরও বেশি। অথচ memo বা লুপে fib(90) লাগে নব্বইটির মতো ধাপ — চোখের পলকেরও কম।

এই অপচয়ের মূল কারণ হলো overlapping subproblems — গাছের বিভিন্ন শাখায় একই প্রশ্ন বারবার। call tree-তে fib(n − 2) আসে fib(n)-এর সরাসরি সন্তান হিসেবে, আবার fib(n − 1)-এর ভেতরেও। নিচের দিকে এই পুনরাবৃত্তি গুণ হতে থাকে। Tower of Hanoi-ও exponential (2ⁿ − 1), কিন্তু সেখানে কোনো অপচয় নেই — প্রতিটি চাল সত্যিই লাগে। Fibonacci-তে আসল কাজ মাত্র n + 1টি আলাদা প্রশ্ন, বাকি সব পুনরাবৃত্তি।

মূল উপলব্ধি: exponential দুই ধরনের — সমস্যা নিজেই কঠিন (Hanoi), অথবা আমাদের সমাধান অপচয়ী (সরল Fibonacci). দ্বিতীয়টি চেনার সবচেয়ে সহজ উপায়: ছোট ইনপুটের call tree এঁকে দেখা, একই ঘর বারবার আসছে কি না।

প্র ০৫বাস্তবের কোন কোন সিস্টেম ভেতরে recursive? রিকার্শন কি শুধু পাঠ্যবইয়ের ধাঁধা?

মোটেই না। যেখানেই ডেটা “নিজের ভেতরে নিজে” — নেস্টেড — সেখানেই রিকার্শন স্বাভাবিকভাবে আসে। কয়েকটি উদাহরণ যা আপনি প্রতিদিন ব্যবহার করেন:

ফাইল সিস্টেম: ফোল্ডারের ভেতরে ফাইল ও আরও ফোল্ডার। Windows-এ একটি ফোল্ডারের Properties-এ মোট মাপ দেখা, Linux-এ du বা rm -r (r মানে recursive!) — সবাই প্রতিটি সাব-ফোল্ডারে ঢুকে একই কাজ করে।
ওয়েবপেজ: HTML-এ ট্যাগের ভেতরে ট্যাগ। ব্রাউজার পেজটিকে একটি গাছে (DOM) সাজায়, আর সেই গাছ ঘোরার স্বাভাবিক উপায় রিকার্শন।
JSON: bKash বা যেকোনো অ্যাপের সার্ভার যে ডেটা পাঠায়, তাতে object-এর ভেতরে object, তালিকার ভেতরে তালিকা। JSON পড়ার প্রোগ্রাম (parser) প্রায়ই recursive.
Compiler: (2 + (3 * (4 - 1))) — বন্ধনীর ভেতরে বন্ধনী। GCC ও Clang দুটোই কোড পড়তে হাতে লেখা “recursive descent parser” ব্যবহার করে: “expression মানে একটি term, তার পরে হয়তো + ও আরেকটি expression” — সংজ্ঞাটিই recursive.
অ্যালগরিদম: merge sort, quick sort, গ্রাফে DFS (পর্ব ৩৮), দাবা বা লুডোর মতো খেলায় সম্ভাব্য চালের গাছ খোঁজা।

বাস্তবের একটি নিরাপত্তা-শিক্ষা: recursive parser-এর গভীরতা নির্ভর করে ইনপুটের ওপর। কেউ ইচ্ছা করে লাখ স্তরের নেস্টেড বন্ধনী বা JSON পাঠালে parser-এর stack ভরে সার্ভার crash করতে পারে — এটি একটি পরিচিত আক্রমণের ধরন। তাই পেশাদার parser-গুলো সর্বোচ্চ নেস্টিং গভীরতার একটি সীমা বেঁধে দেয়, অথবা ঝুঁকিপূর্ণ অংশ লুপ ও নিজের stack দিয়ে লেখে।

মূল উপলব্ধি: ডেটার গঠন recursive হলে কোডও recursive হলে সবচেয়ে পরিষ্কার হয়। কিন্তু যে ইনপুট বাইরের মানুষ পাঠায়, তার গভীরতার ওপর কখনো অন্ধ বিশ্বাস নয় — সীমা বেঁধে দিন।

অনুশীলন

এগুলোর বেশিরভাগে কোড লিখতে হবে না — হাতে-কলমে দেখা আর ভাবাই আসল কাজ।

কাগজে stack আঁকুন: sum(n) ফাংশনটি এমন — n ≤ 0 হলে 0 ফেরত দেয়, নাহলে n + sum(n - 1). sum(3)-এর জন্য প্রতিটি frame কাগজে একটির ওপর আরেকটি আঁকুন, আর ফেরার পথে কোন frame কী ফেরত দেয় লিখুন।

যাওয়ার পথে stack: sum(3) “3 + ?” → sum(2) “2 + ?” → sum(1) “1 + ?” → sum(0). sum(0) base case — 0 ফেরত। এবার ফেরার পথে: sum(1) = 1 + 0 = 1, sum(2) = 2 + 1 = 3, sum(3) = 3 + 3 = 6. একসাথে সর্বোচ্চ ৪টি sum-এর frame ছিল (n = 3 থেকে 0). অর্থাৎ sum(n)-এর গভীরতা n + 1 — sum(১০ লাখ) কেন বিপজ্জনক, এখান থেকেই বোঝা যায়।
বাগ শিকারি: নিচের দুটি countdown ফাংশনে কী সমস্যা? (ক) void cd(int n) { printf("%d\n", n); cd(n - 1); } (খ) void cd(int n) { if (n == 0) return; printf("%d\n", n); cd(n - 2); } — কোন ইনপুটে কী ঘটবে?

(ক) base case-ই নেই — মুখোমুখি আয়না। যেকোনো ইনপুটে সংখ্যা ছাপতে ছাপতে ঋণাত্মকে চলে যাবে, তারপর stack overflow-এ crash. (মজার ব্যাপার: optimization চালু থাকলে compiler এটিকে tail call হিসেবে লুপে বদলে দিতে পারে, তখন crash না করে প্রোগ্রাম অনন্তকাল চলবে — দুটোই ভুল।)

(খ) base case আছে, কিন্তু সবসময় পৌঁছানো যায় না। জোড় সংখ্যায় (৬ → ৪ → ২ → ০) ঠিক চলে; বিজোড়ে (৫ → ৩ → ১ → −১ …) শূন্য টপকে যায়, থামে না। সমাধান: if (n <= 0) return;
বৃদ্ধির হার মাপুন: উপরের fib_calls.c-তে দুই জায়গায় 30-এর বদলে 35 লিখে চালান। সরল ভার্সনে ডাক কত গুণ বাড়ল? চালানোর আগে অনুমান করুন — ১.৬১৮-কে ৫ বার গুণ করলে কত হয়?

n = 35-এ সরল ভার্সনে ডাক হবে ২,৯৮,৬০,৭০৩টি — আগের ২৬,৯২,৫৩৭-এর প্রায় ১১ গুণ। অনুমানও তাই বলে: ১.৬১৮^৫ ≈ ১১.১. অন্যদিকে memo ভার্সনে ডাক ৫৯ থেকে হলো মাত্র ৬৯ — প্রতি n-এ ২টি করে বাড়ে। এক দিকে গুণ, অন্য দিকে যোগ — exponential আর linear বৃদ্ধির পার্থক্য এভাবে নিজের চোখে দেখা যায়। (35-এর বেশি দিলে সরল ভার্সন অনলাইন compiler-এ সময়সীমা পেরিয়ে যেতে পারে।)
৪টি চাকতির Hanoi: কোড না চালিয়ে বলুন — hanoi(4, 'A', 'C', 'B')-এ মোট কয়টি চাল লাগবে, আর একদম প্রথম চালে ছোট চাকতিটি কোথায় যাবে?

চাল লাগবে 2⁴ − 1 = ১৫টি — ৩ চাকতির ৭টি চাল দুবার, মাঝে বড়টির একটি (৭ + ১ + ৭)। প্রথম চাল: hanoi(4, A, C, B) ডাকে hanoi(3, A, B, C), সেটি ডাকে hanoi(2, A, C, B), সেটি ডাকে hanoi(1, A, B, C) — অর্থাৎ ছোট চাকতি প্রথমে যাবে B-তে, C-তে নয়! নিয়মটি: চাকতির সংখ্যা জোড় হলে ছোটটি প্রথমে সাহায্যকারী খুঁটিতে যায়, বিজোড় হলে সরাসরি গন্তব্যে (৩ চাকতিতে যেমন C-তে গিয়েছিল)।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমfact(3) চলার ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

main ডাকে fact(3), তার জন্য নতুন frame তৈরি হয়
fact(3) “3 × ?” রেখে ডাকে fact(2)
fact(2) “2 × ?” রেখে ডাকে fact(1)
fact(1) base case-এ পৌঁছে 1 ফেরত দেয়
fact(2) হিসাব করে 2 × 1 = 2 ফেরত দেয়
fact(3) হিসাব করে 3 × 2 = 6, main উত্তর পায়

একটি recursive ফাংশনে base case-এর আসল কাজ কী?

ফাংশনকে দ্রুত করা
ডাকাডাকি থামানো — সবচেয়ে ছোট রূপের উত্তর সরাসরি দেওয়া
ফাংশনকে নিজেকে ডাকতে বাধ্য করা
stack-এর মেমরি খালি করা

int f(int n) { return n + f(n - 1); } — f(5) ডাকলে কী ঘটবে?

15 ফেরত দেবে
compile হবে না
ডাক থামবে না, stack ভরে প্রোগ্রাম crash করবে
0 ফেরত দেবে

fact(4) চলার সময় এক মুহূর্তে সর্বোচ্চ কয়টি fact-এর stack frame একসাথে মেমরিতে থাকে?

১টি
২টি
৩টি
৪টি

সরল recursive fib(5)-এ fib(2) কতবার হিসাব হয়?

১ বার
২ বার
৩ বার
৫ বার

৪টি চাকতির Tower of Hanoi সমাধানে সবচেয়ে কম কয়টি চাল লাগে?

৮টি
১৫টি
১৬টি
৩১টি

AI ১ থেকে n পর্যন্ত যোগফলের একটি recursive ফাংশন দিল। n = ১০০-তে ঠিক চলে, কিন্তু n = ১০ লাখে crash করে। সবচেয়ে ভালো সমাধান কী?

একটি সাধারণ লুপ দিয়ে লেখা
অপারেটিং সিস্টেমের stack-এর মাপ বাড়িয়ে দেওয়া
memoization যোগ করা
-O2 দিয়ে compile করে ধরে নেওয়া যে compiler ঠিক করে দেবে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

রিকার্শন মানে বড় সমস্যার উত্তর পেতে একই সমস্যার ছোট রূপের জন্য নিজেকে ডাকা।
দুটি অংশ বাধ্যতামূলক: base case আর recursive case — এবং প্রতিটি ইনপুট থেকে base case-এ পৌঁছানো নিশ্চিত হতে হবে।
প্রতিটি ডাকে নতুন stack frame; গভীরতা বেশি হলে বা থামার জায়গা না থাকলে stack overflow.
একই উপ-সমস্যা বারবার এলে খরচ exponential — উত্তর লিখে রাখুন (memoization) অথবা লুপ ব্যবহার করুন।
নেস্টেড গঠন ও divide and conquer-এ রিকার্শন; লম্বা সরল শিকলে লুপ। C tail call-এর নিশ্চয়তা দেয় না।

পরের পর্বে: মডিউল ২ শেষ — ভাষার মূল যন্ত্রপাতি এখন আপনার হাতে। এবার শুরু C-এর হৃদয়, মেমরি। প্রথমেই অ্যারে: একই ধরনের অনেক ডেটা পাশাপাশি সাজানো ঘরে — আর আজকের memo টেবিলটি আসলে কী ছিল, সেটাও তখন পরিষ্কার হবে।

রিকার্শন — যে ফাংশন নিজেকেই ডাকে

এই পর্বে যা শিখবেন

১ · টিকিটের লাইনে একটি প্রশ্ন

২ · দুটি অংশ: থামার জায়গা আর ছোট হওয়ার ধাপ

🛑 Base case

🔁 Recursive case

যেকোনো recursive ফাংশন লেখার তিন প্রশ্ন

৩ · ভেতরে কী ঘটে — প্রতিটি ডাকে নতুন stack frame

৪ · Stack overflow — যখন নামা আর থামে না

🪞 Base case নেই বা পৌঁছানো যায় না

📏 ইনপুট খুব বড়

৫ · Fibonacci — একই কাজ বারবার করার দাম

৬ · Tower of Hanoi — যেখানে রিকার্শনই সবচেয়ে সহজ পথ

৭ · রিকার্শন নাকি লুপ — কখন কোনটি

Tail call — যে রিকার্শন লুপ হয়ে যেতে পারে

৮ · AI-এর যুগে রিকার্শন যাচাই

AI-এর রিকার্শনে যেসব ভুল প্রায়ই দেখা যায়

AI-এর রিকার্শন হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ