সি প্রোগ্রামে রিকার্সিভ ফাংশন সহ সহায়ক স্থান?

এখানে আমরা দেখব কিভাবে রিকার্সিভ ফাংশন কলের জন্য সহায়ক স্থান প্রয়োজন। এবং সাধারণ ফাংশন কল থেকে এটি কীভাবে আলাদা?

ধরুন আমাদের নিচের মত একটি ফাংশন আছে −

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

এই ফাংশনটি পুনরাবৃত্ত ফাংশন। যখন আমরা এটিকে ফ্যাক্ট(5) এর মতো বলি, তখন এটি স্ট্যাকের ভিতরে ঠিকানাগুলিকে নীচের মত সংরক্ষণ করবে −

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

পুনরাবৃত্ত ফাংশন বারবার নিজেকে কল করা হয়, ঠিকানা স্ট্যাক যোগ করা হয়. সুতরাং যদি ফাংশনটিকে n বার বারবার বলা হয়, এটি O(n) সহায়ক স্থান নেবে। কিন্তু এর মানে এই নয় যে যদি একটি স্বাভাবিক ফাংশনকে n বার বলা হয়, তাহলে স্থানের জটিলতা হবে O(n)। সাধারণ ফাংশনের জন্য যখন এটি কল করা হয়, ঠিকানাটি স্ট্যাকের মধ্যে পুশ করা হয়। এর পরে এটি সম্পূর্ণ হলে, এটি স্ট্যাক থেকে ঠিকানা পপ করবে এবং ইনভোকার ফাংশনে আসবে। তারপর আবার কল করুন। সুতরাং এটি O(1) হবে।