ভূমিকা
রিকার্সিভ ফাংশন কল করার সময় প্রতিটি কলের রিটার্ন অ্যাড্রেস স্টকে (stack) সংরক্ষিত হয়। ফলে n-ডেপথ রিকার্সনের জন্য O(n) অক্সিলিয়ারি স্পেস লাগে। অন্যদিকে, সাধারণ ফাংশন কলে কল শেষ হলে স্টক থেকে পপ হয়ে যায়, তাই O(1) স্পেস।
উদাহরণ: ফ্যাক্টোরিয়াল
long fact(int n) {
if (n==0 || n==1) return 1;
return n * fact(n-1);
}
// fact(5) কল করলে:
// fact(5) → fact(4) → fact(3) → fact(2) → fact(1)
// ৫টি স্টেক ফ্রেম তৈরি হবে → O(n) স্পেস
সাধারণ ফাংশন কল
void foo() { ... }
void bar() {
for (int i=0; i<5; i++) foo(); // প্রতিবার foo() কল হলে স্টেক পুশ-পপ হয়
}
// সর্বোচ্চ ১টি স্টেক ফ্রেমই থাকে একসাথে → O(1) স্পেস
নিষ্কর্ষ
রিকার্সন ব্যবহার করার সময় স্পেস কমপ্লেক্সিটি বিবেচনা করা জরুরি, বড় ইনপুটের জন্য স্টেক ওভারফ্লো হতে পারে।
