रिकर्शन: लौटे मान और बची हुई गणना

पाठ 16 / 1613 मिनटमुफ़्त

लौटे मान के बाद caller का बचा हुआ काम शुरू होता है

पहले रिकर्शन: आधार स्थिति और कॉल स्टैक पढ़ें। आपको पता होना चाहिए कि सामान्य पैरामीटर एक कॉल का अपना होता है और अंदर वाली कॉल लौटने पर प्रतीक्षा कर रहा caller फिर आगे चलता है। पूर्णांक अंकगणित और if कथन भी आने चाहिए। ऐरे और पॉइंटर की ज़रूरत नहीं है।

इस पाठ का विषय वापसी के समय गणना पूरी करना (unwinding) है: रिकर्सिव कॉल लौटने पर रुके हुए काम को पूरा करना। आप caller के अपने मान सुरक्षित रखेंगे, ठीक वही बची हुई गणना करेंगे और लौटे परिणाम से बाद की शर्त जाँचेंगे। रिकर्शन रोकने की शर्तों का चुनाव अलग पाठ में है। ये छोटे उदाहरण शाखाओं वाले रिकर्शन या समय/स्थान के औपचारिक विश्लेषण को पूरा नहीं करते।

कोड के लिए शर्तें

हम C11 और आरंभ किए हुए सामान्य automatic int ऑब्जेक्ट इस्तेमाल करते हैं। प्रश्न में अलग सीमा न दी हो तो शुरुआती इनपुट 0 से 4 तक के पूर्णांक हैं। सबसे अंदर वाला आर्ग्युमेंट 0 है, हर रिकर्सिव कॉल में n - 1 दिया जाता है और सभी दिखाए गए परिणाम int की न्यूनतम अनिवार्य सीमा में भी आते हैं। static स्थानीय चर, वैश्विक चर या पॉइंटर से साझा लक्ष्य नहीं हैं। मनमाने इनपुट या किसी कार्यान्वयन की अधिकतम रिकर्शन गहराई का दावा नहीं है।

आउटपुट का अनुमान लगाएँ। यह केवल आर्ग्युमेंट के मानों का योग नहीं है।

#include <stdio.h>

int score(int n) {
    if (n == 0) {
        return 1;
    }
    int child = score(n - 1);
    return 2 * child + n;
}

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

आधार स्थिति 1 देती है। बाकी हर कॉल को अंदर वाली कॉल की प्रतीक्षा करनी है, लौटे मान को दोगुना करना है और अपना n जोड़ना है। प्रतीक्षा कर रही कॉल पर लिखें: 2 × [अंदर वाली कॉल का परिणाम] + मेरा n। खाली परिणाम की जगह अंदर वाली कॉल का आर्ग्युमेंट न रख दें।

हल किया ट्रेस हर caller की अपनी बाकी गणना

चरण	इस कॉल का अपना n	अवस्था या गणना
`score(3)` में प्रवेश	3	`score(2)` की प्रतीक्षा; बाकी गणना `2 * child + 3`
`score(2)` में प्रवेश	2	`score(1)` की प्रतीक्षा; बाकी गणना `2 * child + 2`
`score(1)` में प्रवेश	1	`score(0)` की प्रतीक्षा; बाकी गणना `2 * child + 1`
`score(0)` में प्रवेश	0	तुरंत 1 लौटाए
`score(1)` फिर चले	1	`child = 1` का आरंभीकरण; `2 * 1 + 1 = 3` लौटाए
`score(2)` फिर चले	2	`child = 3` का आरंभीकरण; `2 * 3 + 2 = 8` लौटाए
`score(3)` फिर चले	3	`child = 8` का आरंभीकरण; `2 * 8 + 3 = 19` लौटाए
`main` फिर चले	—	`answer = 19` रखे, फिर `19` छापे

n = 3 वाली कॉल में अंततः child का मान 8 है, 2 नहीं। संख्या 2 दूसरी कॉल को दिया गया आर्ग्युमेंट थी; 8 उस कॉल का निकाला और लौटाया हुआ परिणाम है। दोनों भूमिकाएँ अलग हैं। n = 3 वाली कॉल का अपना पैरामीटर पूरे समय 3 रहता है।

हर int child = ... का आरंभीकरण तभी पूरा होता है जब कॉल व्यंजक का मान मिल जाए। उसमें अपने आप शुरुआती शून्य नहीं रखा जाता। आधार स्थिति वाला रास्ता इस घोषणा तक पहुँचने से पहले लौट जाता है। return ठीक ऊपर वाले caller को परिणाम देता है; यहाँ केवल main का printf कुछ दिखाता है।

सरल करने से पहले कोष्ठक सहित विस्तार करें

score(3) का सटीक विस्तार है:

2 * (2 * (2 * 1 + 1) + 2) + 3 = 19

सबसे अंदर का 1 आधार स्थिति का परिणाम है; जोड़े जाने वाले 1, 2 और 3 अलग-अलग caller के हैं। सारी संख्याएँ पहले जोड़कर केवल एक बार दोगुना करने से गणना बदल जाएगी। कोष्ठक बताते हैं कि कौन-सी गणना किस लौटे मान पर निर्भर है।

घटाव में यह गलती और साफ़ दिखती है। इस अलग प्रोग्राम का अनुमान लगाएँ।

#include <stdio.h>

int difference(int n) {
    if (n == 0) {
        return 0;
    }
    int child = difference(n - 1);
    return n - child;
}

int main(void) {
    printf("%d\n", difference(3));
    return 0;
}

कॉल 3, 2, 1, 0 आर्ग्युमेंट के साथ अंदर जाती हैं। लौटते समय परिणाम हैं:

difference(0) = 0
difference(1) = 1 - 0 = 1
difference(2) = 2 - 1 = 1
difference(3) = 3 - 1 = 2

इसलिए 2 छपता है। विस्तार 3 - (2 - (1 - 0)) है, 3 - 2 - 1 - 0 नहीं। प्रतीक्षा कर रहा caller पूरे लौटे परिणाम को घटाता है, अंदर जाते समय दिखे हर आर्ग्युमेंट को अलग-अलग नहीं। घटाव के कोष्ठक मनमाने ढंग से बदल नहीं सकते।

वापसी का ट्रेस बनाने की दोहराने योग्य विधि

प्रवेश पर इस कॉल का आर्ग्युमेंट और आगे काम आने वाले आरंभ किए स्थानीय चर लिखें।
अंदर वाली कॉल के लिए रुका हुआ सटीक कथन चिन्हित करें। परिणाम की जगह खाली रखें; कोई मान न गढ़ें।
अंदर वाली कॉल पूरी करें। उसका लौटाया मान प्रतीक्षा कर रही कॉल के परिणाम वाले स्थान में रखें।
उस caller का अगला कथन चलाएँ। उसके अपने पैरामीटर और स्थानीय चर लें, समाप्त हो चुकी अंदर वाली कॉल के पैरामीटर नहीं।
बाद की शर्त अब जाँचें, उस समय की वास्तविक अवस्था से। चल चुका return इस कॉल को समाप्त करता है; आगे के किसी कथन का return उसे बदलता नहीं।
निकाला हुआ मान अगली प्रतीक्षा कर रही कॉल को दें और यही प्रक्रिया दोहराएँ।

फ़ंक्शन अंदर वाली कॉल का मान बिना बदले लौटा सकता है, उसे गुणा या घटा सकता है, या उससे शाखा चुन सकता है। ऐसा कोई नियम नहीं कि हर रिकर्सिव caller को 1 जोड़ना चाहिए, और न यह कि हर आधार स्थिति 0 लौटाए। कौन-सी गणना करनी है, यह समस्या की शर्तें तय करती हैं।

कॉल स्टैक का चित्र यहाँ भी तार्किक ट्रेस का मॉडल है। ये रिकॉर्ड और गिनतियाँ भौतिक भंडारण, कंपाइलर के अनुकूलन या स्टैक की बाइट-संख्या तय नहीं करते। हर उदाहरण में आधार स्थिति के अलावा एक कॉल अधिकतम एक रिकर्सिव कॉल करती है; एक ही व्यंजक में कई रिकर्सिव कॉल के मूल्यांकन-क्रम के बारे में कोई अनुमान ज़रूरी नहीं है।

एक सटीक उपमा

गणना की पर्चियों का ढेर सोचें। हर पर्ची का अपना निर्देश है, जैसे “अगली पर्ची से लौटे परिणाम को दोगुना करके अपना 3 जोड़ो।” परिणाम आने तक उसका खाना खाली रखें। परिणाम मिलते ही इस पर्ची की गणना पूरी करें और उत्तर नीचे वाली पर्ची को दें।

अंदर वाली पर्ची का इनपुट उस पर लिखा अनुरोध है; लौटाया गया मान तैयार उत्तर है। दोनों का बराबर होना ज़रूरी नहीं। यह उपमा निर्भरता और caller की सुरक्षित अवस्था समझाती है। इसका अर्थ यह नहीं कि वास्तविक C कार्यान्वयन को पर्चियों जैसे रिकॉर्ड रखने ही पड़ते हैं या प्रतीक्षा कर रहे caller एक साथ चलते हैं।

मुख्य बातें बाकी गणना ठीक रखें

आर्ग्युमेंट: कॉल में दिया मान। लौटाया गया मान: उस कॉल से निकला परिणाम।
इन उदाहरणों में प्रतीक्षा कर रहा caller अपना सामान्य पैरामीटर और ज़रूरी automatic स्थानीय चर रखता है।
caller का रुका आरंभीकरण और आगे के कथन पूरे करने से पहले अंदर वाली कॉल पूरी करें।
कोष्ठक बचाएँ: n - child का अर्थ सभी कॉल के आर्ग्युमेंट को एक सपाट क्रम में घटाना नहीं है।
बाद की शाखा लौटे मान पर निर्भर हो सकती है, केवल शुरुआती आर्ग्युमेंट पर नहीं।
आधार स्थिति के मान और वापसी की गणना फ़ंक्शन की शर्तों से तय होते हैं; 0 या +1 कोई सार्वभौमिक नियम नहीं।
सीमा: छोटे, सीमित इनपुट पर एक अंदर वाली कॉल वाले रिकर्शन के लौटे मानों का विश्लेषण; पूरा रिकर्शन नहीं।

छह मौलिक अभ्यास प्रश्न

हर प्रश्न में चार विकल्पों में से ठीक एक चुनें। ये नए सीखने के अभ्यास हैं, आधिकारिक पिछले वर्ष के प्रश्न या पूरा मॉक पेपर नहीं। प्रश्न 1 और 3 के लिए पहले की हूबहू परिभाषाएँ लें। प्रश्न 6 रिक्त स्थान वाला फ़ंक्शन अंश है; इसे किसी प्रोग्राम के भाग के रूप में संकलित करने से पहले व्यंजक भरें।

प्रश्न 1

हल किए उदाहरण की score परिभाषा को बिना बदले इस्तेमाल करें। score(4) क्या मान लौटाता है?

A. 38 B. 42 C. 23 D. 41

प्रश्न 2

यह प्रोग्राम क्या छापता है? इसके अनुमत शुरुआती इनपुट 0 से 4 तक के पूर्णांक हैं।

#include <stdio.h>

int digits(int n) {
    if (n == 0) {
        return 0;
    }
    int child = digits(n - 1);
    return 10 * child + n;
}

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

A. 40 B. 10 C. 1234 D. 4321

प्रश्न 3

दूसरे हल किए उदाहरण की difference परिभाषा इस्तेमाल करें। difference(4) क्या लौटाता है?

A. 2 B. 10 C. -2 D. 4

प्रश्न 4

यह प्रोग्राम क्या छापता है? लौटाते समय अंदर वाली कॉल का परिणाम बदलना ज़रूरी नहीं है।

#include <stdio.h>

int carry(int n) {
    if (n == 0) {
        return 4;
    }
    int child = carry(n - 1);
    return child;
}

int main(void) {
    printf("%d\n", carry(3));
    return 0;
}

A. 16 B. 7 C. 0 D. 4

प्रश्न 5

यह प्रोग्राम क्या छापता है? हर कॉल को अंदर वाली कॉल का मान मिलने के बाद ही child < 5 की शर्त जाँचें।

#include <stdio.h>

int choose(int n) {
    if (n == 0) {
        return 2;
    }
    int child = choose(n - 1);
    if (child < 5) {
        return child + 3;
    }
    return child - 1;
}

int main(void) {
    printf("%d\n", choose(3));
    return 0;
}

A. 5 B. 4 C. 7 D. 2

प्रश्न 6

0 से 6 तक के शुरुआती पूर्णांक के लिए odd_total(n) को पहले n धनात्मक विषम पूर्णांकों का योग लौटाना है। पहले n - 1 पदों के बाद अगला विषम पूर्णांक 2 * n - 1 है। कौन-सा व्यंजक हर अनुमत इनपुट के लिए फ़ंक्शन सही पूरा करता है?

int odd_total(int n) {
    if (n == 0) {
        return 0;
    }
    int child = odd_total(n - 1);
    return EXPRESSION;
}

A. child + (2 * n - 1) B. 2 * child + n C. n * (child + 1) D. child + n

उत्तर और गलत रास्तों की वजह

उत्तर 1: B

B सही है। score(3) से 19 लौटता है, इसलिए प्रतीक्षा कर रही n = 4 वाली कॉल 2 * 19 + 4 = 42 लौटाती है। A में 19 दोगुना किया गया है, लेकिन इस कॉल का 4 नहीं जोड़ा गया। C में 19 में 4 जोड़ा है, लेकिन दोगुना नहीं किया। D प्रतीक्षा कर रही कॉल के n = 4 की जगह अंदर वाली कॉल का n = 3 इस्तेमाल करता है।

उत्तर 2: C

C सही है। n = 0 से 4 तक लौटते समय मान 0, 1, 12, 123, 1234 मिलते हैं। हर caller, अंदर वाली कॉल के पूरे लौटे मान को 10 से गुणा करता है, फिर अपना n जोड़ता है। A, 10 * 4 पर रुक जाता है। B अंदर वाली कॉल के मान को 10 से गुणा किए बिना इनपुट जोड़ता है। D नीचे जाती कॉल के आर्ग्युमेंट को ही उत्तर मान लेता है; उन कॉल के दौरान कोई printf नहीं चलता।

उत्तर 3: A

A सही है। n = 0, 1, 2, 3, 4 के लिए लौटे मान 0, 1, 1, 2, 2 हैं। अंतिम गणना 4 - difference(3) = 4 - 2 है। B घटाने का क्रम अपनाने के बजाय सारे धनात्मक इनपुट जोड़ता है। C तब मिलता है जब कोष्ठक वाला व्यंजक गलत तरीके से 4 - 3 - 2 - 1 - 0 बना दिया जाए। D अंदर वाली कॉल से लौटे मान को छोड़ देता है।

उत्तर 4: D

D सही है। आधार स्थिति वाली कॉल 4 लौटाती है; प्रतीक्षा कर रहे तीनों caller वही मान बिना बदले लौटाते हैं। A हर कॉल के लिए 4 जोड़ता है, लेकिन कोड में ऐसा कोई जोड़ नहीं है। B शुरुआती n = 3 जोड़ता है, जो कोड में नहीं है। C मानता है कि आधार स्थिति हमेशा 0 लौटाएगी; ऐसा कोई नियम नहीं है।

उत्तर 5: C

C सही है। n = 0 वाली कॉल 2 लौटाती है। n = 1 पर child = 2 < 5 है, इसलिए 5 लौटता है। n = 2 पर child = 5, 5 से कम नहीं है, इसलिए 4 लौटता है। n = 3 पर child = 4 < 5 है, इसलिए 7 लौटता है। A, n = 1 के बाद रुक जाता है; B, n = 2 के बाद; D प्रतीक्षा कर रहा काम किए बिना आधार स्थिति का मान लौटा देता है। जाँच child की है, n की नहीं।

उत्तर 6: A

A सही है। अंदर वाली कॉल पहले n - 1 धनात्मक विषम पूर्णांकों का योग लौटाती है; ठीक छूटा हुआ पद 2 * n - 1 जोड़ें। आधार स्थिति खाली योग 0 लौटाती है। n = 3 पर सही परिणाम 1 + 3 + 5 = 9 है। इसी इनपुट पर B से 11, C से 15 और D से 6 मिलता है। केवल n = 1 की जाँच से चारों विकल्प अलग नहीं होंगे; वहाँ चारों 1 लौटाते हैं।

आगे बढ़ने से पहले

लौटे मान की जगह आर्ग्युमेंट रख दिया हो तो “भेजा गया” और “मिला हुआ” के अलग कॉलम बनाएँ। caller का n आधार स्थिति के शून्य में बदल दिया हो तो हर कॉल का अलग रिकॉर्ड फिर बनाएँ। घटाव गलत हो तो सबसे अंदर वाला परिणाम मिलने तक सभी कोष्ठक रखें। शर्त गलत चुनी हो तो शाखा चुनने से पहले जाँच के बगल में वास्तविक child मान लिखें।

अगले चरण में स्पष्ट खाली-प्रीफ़िक्स आधार स्थिति वाले सीमित ऐरे helper पर लौटे मानों का यह ट्रेस अपनाएँ। शाखाओं वाला रिकर्शन, recurrence हल करना और संसाधनों का औपचारिक विश्लेषण बाद के पाठों के विषय हैं।

स्रोत और पाठ की सीमा

13 अक्टूबर 2026 को सत्यापित आधिकारिक GATE 2027 CS पाठ्यक्रम में Programming and Data Structures के अंतर्गत रिकर्शन शामिल है। यह स्रोत केवल विषय की प्रासंगिकता बताता है। पाठ, प्रोग्राम और प्रश्न मौलिक शिक्षण सामग्री हैं; C11 शिक्षण के लिए चुना गया है, आधिकारिक परीक्षा का भाषा-संस्करण बताने के लिए नहीं। यह पाठ किसी मौजूदा कोर्स का वर्ष या पहचान नहीं बदलता।

प्रगति सहेजने के लिए साइन इन करें। साइन इन

ParikshaPDF Editorial Team · अपडेट: 13 अक्टूबर 2026

Graduate Aptitude Test in Engineering (GATE) का अगला विषयसामान्य अभिरुचि