परिचय
यहां हम देखेंगे कि रिकर्सिव फ़ंक्शन कॉल के लिए सहायक स्पेस कैसे आवश्यक है। और यह सामान्य फ़ंक्शन कॉल से कैसे भिन्न है?
उदाहरण
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)
चूंकि रिकर्सिव फ़ंक्शन स्वयं को बार-बार कॉल करते हैं, पते स्टैक में जुड़ते जाते हैं। इसलिए यदि फ़ंक्शन n बार रिकर्सिवली कॉल किया जाता है, तो यह O(n) सहायक स्पेस लेगा। लेकिन इसका मतलब यह नहीं है कि यदि एक सामान्य फ़ंक्शन को n बार कॉल किया जाता है, तो स्पेस जटिलता O(n) होगी। सामान्य फ़ंक्शन के लिए जब इसे कॉल किया जाता है, तो पता स्टैक में डाला जाता है। उसके बाद जब यह पूरा हो जाता है, तो यह स्टैक से पता पॉप करेगा और इनवोकर फ़ंक्शन में आ जाएगा। फिर से कॉल करें। इसलिए यह O(1) होगा।
