विषय पर बढ़ें

अंतिम अद्यतन：2026-10-12

C++ टेल रिकर्शन

टेल रिकर्शन ऑप्टिमाइज़ेशन एक विशेष ऑप्टिमाइज़ेशन तकनीक है जो recursive फ़ंक्शन पर लागू होती है, यह recursive कॉल के stack स्पेस उपयोग को बहुत कम कर सकती है। टेल रिकर्शन ऑप्टिमाइज़ेशन के ज़रिए कंपाइलर टेल रिकर्शन निष्पादित करते समय नया stack frame बनाने से बचकर मौजूदा stack frame को सीधे पुनः उपयोग कर सकता है, जिससे stack overflow का ख़तरा घटता है और परफ़ॉर्मेंस बढ़ती है।

टेल रिकर्शन क्या है?

Recursive कॉल वापस आने पर कोई अन्य ऑपरेशन निष्पादित करने की ज़रूरत न हो, ऐसी रिकर्शन को टेल रिकर्शन कहते हैं। ऐसी स्थिति में कंपाइलर रिकर्शन की जगह एक लूप स्ट्रक्चर का उपयोग करके बार-बार फ़ंक्शन कॉल के ओवरहेड से बच सकता है।

नॉन-टेल रिकर्शन का उदाहरण (फ़िबोनैचि संख्या)

आपके द्वारा दिया गया fibonacci_non_tail() फ़ंक्शन एक स्टैंडर्ड नॉन-टेल रिकर्शन इम्प्लीमेंटेशन है:

int fibonacci_non_tail(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_non_tail(n - 1) + fibonacci_non_tail(n - 2);
}

इस इम्प्लीमेंटेशन में, recursive कॉल fibonacci_non_tail(n - 1) और fibonacci_non_tail(n - 2) के बाद भी उनके परिणामों को जोड़ना बाकी रहता है, इसलिए यह टेल रिकर्शन नहीं है। हर कॉल को कॉन्टेक्स्ट जानकारी सहेजनी पड़ती है ताकि रिकर्शन से वापसी के बाद गणना जारी रखी जा सके, जिसके कारण stack स्पेस तेज़ी से बढ़ता है।

टेल रिकर्शन ऑप्टिमाइज़ेशन का उदाहरण

fibonacci_tail() टेल रिकर्शन तरीके का उपयोग करता है:

int fibonacci_tail_helper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    return fibonacci_tail_helper(n - 1, b, a + b);
}

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

यहाँ fibonacci_tail_helper() टेल रिकर्शन है। आप देख सकते हैं कि recursive कॉल fibonacci_tail_helper(n - 1, b, a + b) के बाद फ़ंक्शन को कोई और काम नहीं करना है, वह सीधे recursive कॉल का परिणाम लौटाता है। इसलिए recursive कॉल फ़ंक्शन के "टेल (tail)" में स्थित है, उसके बाद निष्पादित होने वाला कोई अतिरिक्त ऑपरेशन नहीं है।

टेल रिकर्शन ऑप्टिमाइज़ेशन के फ़ायदे

  • stack स्पेस उपयोग में कमी: recursive कॉल का कॉन्टेक्स्ट सहेजने की ज़रूरत न होने के कारण कंपाइलर stack frame का पुनः उपयोग कर सकता है, जिससे stack स्पेस का फैलाव टलता है।
  • stack overflow की रोकथाम: टेल रिकर्शन ऑप्टिमाइज़ेशन से रिकर्शन की गहराई बहुत बड़ी होने पर भी stack overflow नहीं होता।
  • ज़्यादा कुशल: टेल रिकर्शन ऑप्टिमाइज़ेशन सपोर्ट करने वाले कंपाइलरों में टेल रिकर्शन की परफ़ॉर्मेंस iterative इम्प्लीमेंटेशन के करीब होती है, recursive फ़ंक्शन कॉल का ओवरहेड समाप्त हो जाता है।

परफ़ॉर्मेंस टेस्ट

आख़िर में ऊपर दिए गए कोड पर एक benchmark किया गया, जिसमें पाया गया कि इस स्थिति में टेल रिकर्शन ऑप्टिमाइज़ेशन बहुत उपयोगी है, परफ़ॉर्मेंस का अंतर साफ़ दिखता है!

संबंधित विषय

टिप्पणियाँ