रिकर्शन: आधार स्थिति और कॉल स्टैक

एक फ़ंक्शन और कई अधूरी कॉल

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

इस पाठ के अंत तक आप आधार स्थिति पहचान सकेंगे, समझा सकेंगे कि दिए गए रिकर्सिव चरण वहाँ क्यों पहुँचते हैं, और हर कॉल का अलग रिकॉर्ड रखते हुए लौटे मानों का ट्रेस बना सकेंगे। यह प्रत्यक्ष रिकर्शन का परिचय है, जिसमें आधार स्थिति के अलावा हर कॉल अधिकतम एक रिकर्सिव कॉल करती है। इससे रिकर्शन, डेटा संरचनाएँ या GATE CS पूरा नहीं होता।

कोड के लिए हमारी शर्तें

हम C11, आरंभ किए हुए सामान्य automatic int ऑब्जेक्ट और छोटे, निरूपण योग्य परिणाम इस्तेमाल करते हैं। sum_to के लिए केवल 0 से 6 तक के शुरुआती पूर्णांक लें। बाकी उदाहरणों में इनपुट अलग से दिए गए हैं। इनमें static स्थानीय चर, वैश्विक चर या पॉइंटर से साझा लक्ष्य नहीं हैं। यह न मानें कि हर संभव signed integer सुरक्षित इनपुट है या कितनी भी गहरी रिकर्शन चल सकती है।

इस प्रोग्राम से छपने वाली दो संख्याओं का अनुमान लगाएँ। क्या caller का n शून्य हो जाता है?

#include <stdio.h>

int sum_to(int n) {
    if (n == 0) {
        return 0;
    }
    int smaller = sum_to(n - 1);
    return n + smaller;
}

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

रिकर्सिव फ़ंक्शन स्वयं को कॉल करता है; यहाँ यह काम sum_to(n - 1) करता है। हर कॉल का अपना सामान्य पैरामीटर n है। व्यंजक n - 1 आर्ग्युमेंट का मान निकालता है; वह caller के n में नया मान असाइन नहीं करता।

आधार स्थिति (base case) वह रास्ता है जो दूसरी रिकर्सिव कॉल किए बिना लौटता है। यहाँ n == 0 पर 0 लौटता है। रिकर्सिव स्थिति (recursive case) पहले छोटे इनपुट वाली कॉल से परिणाम लेती है, फिर उसमें इस कॉल का अपना n जोड़ती है। अंदर वाली कॉल लौटे बिना smaller का शुरुआती मान तैयार नहीं होता। उसे पहले से निकला हुआ शून्य न मानें।

हल किया ट्रेस कॉल के अंदर जाएँ और लौटे मान वापस लाएँ

main से शुरू करें: n = 3 है; answer का आरंभीकरण प्रतीक्षा कर रहा है।

सबसे अंदर वाली कॉल से 0 लौटने पर सभी caller समाप्त नहीं होते। केवल वही कॉल समाप्त होती है और उसके ठीक ऊपर वाली कॉल को आवश्यक मान मिलता है। फिर हर रुका हुआ जोड़, कॉल के प्रवेश-क्रम से उलटे क्रम में पूरा होता है। helper कुछ नहीं छापता; अंतिम पंक्ति main का printf छापता है।

कॉल स्टैक क्या दर्ज करता है

ट्रेस बनाने के लिए सक्रिय कॉल के रिकॉर्ड का एक स्टैक रखें। हर रिकॉर्ड को फ़्रेम (frame) कह सकते हैं। इसमें उस कॉल के ज़रूरी पैरामीटर, स्थानीय चर और दोबारा चलने का स्थान दर्ज होता है। अंदर वाली कॉल चल रही हो तो caller भी सक्रिय है, लेकिन प्रतीक्षा कर रहा है। सबसे बाद में शुरू हुई अधूरी कॉल के पूरा होने पर ही उसकी प्रतीक्षा कर रही कॉल आगे बढ़ सकती है: सबसे बाद में अंदर, सबसे पहले बाहर।

sum_to(0) के लौटने से ठीक पहले सबसे पुरानी से सबसे नई कॉल तक तार्किक स्टैक पढ़ें:

sum_to(3) → sum_to(2) → sum_to(1) → sum_to(0)

आधार स्थिति वाली कॉल समेत चार सक्रिय sum_to कॉल हैं। इस सीधी शृंखला में sum_to की कुल कॉल भी चार हैं। दोनों गिनतियों में main और लाइब्रेरी कॉल न जोड़ें। कुल कॉल और एक समय पर अधिकतम सक्रिय कॉल अलग माप हैं; यहाँ बराबरी होने से यह शाखाओं वाले रिकर्शन का सामान्य नियम नहीं बन जाता।

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

यह आधार स्थिति क्यों मिलती है

sum_to के अनुमत इनपुट में शुरुआती n शून्य या धनात्मक है। n > 0 हो तो अगला आर्ग्युमेंट n - 1 है, जो छोटा और अभी भी शून्य या धनात्मक पूर्णांक है। सीमित बार घटाने के बाद 0 आता है और वहाँ कोई रिकर्सिव कॉल नहीं होती। सीमा पर sum_to(0) की केवल एक invocation होती है; वह कोई रिकर्सिव कॉल किए बिना तुरंत 0 लौटाती है।

दोनों बातें ज़रूरी हैं: रुकने की स्थिति हो और अनुमत इनपुट के लिए अगला चरण उसकी ओर बढ़े। इसी कोड को -1 से शुरू करें तो बार-बार 1 घटाने से 0 नहीं आएगा। यह इनपुट हमारी शर्तों के बाहर है। इसके लिए कोई निश्चित संख्यात्मक परिणाम न बताएँ: वास्तविक निष्पादन संसाधन खत्म होने से विफल हो सकता है या आगे चलकर अमान्य signed अंकगणित तक पहुँच सकता है। इसी तरह n - 1 की जगह n लिखने से धनात्मक इनपुट पर कोई प्रगति नहीं होगी।

एक सटीक उपमा

काम के कार्डों का ढेर सोचें। 3 वाला कार्ड कहता है, “2 वाले कार्ड का परिणाम आने दो, फिर उसमें अपना 3 जोड़ूँगा।” 2 वाला कार्ड 1 की प्रतीक्षा करता है; 1 वाला 0 की। 0 वाले कार्ड का उत्तर पहले से 0 है। सबसे नए कार्ड का काम पूरा करें, उसका उत्तर ठीक नीचे वाले कार्ड को दें और आगे बढ़ें।

हर कार्ड अपनी संख्या रखता है। सबसे नए कार्ड पर 0 लिखने से सबसे पुराने कार्ड का 3 नहीं मिटता। कार्ड अलग अवस्था और रुके हुए काम को समझाते हैं; वे यह दावा नहीं करते कि C में वास्तव में ऐसे कार्ड जैसे रिकॉर्ड रखना अनिवार्य है या रिकर्सिव कॉल एक साथ चलती हैं।

मुख्य बातें अभ्यास से पहले पढ़ें

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

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

हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न के चार विकल्प हैं। ये नए सीखने के अभ्यास हैं, आधिकारिक पिछले वर्ष के प्रश्न या पूरा मॉक पेपर नहीं। उत्तर देखने से पहले कॉल और वापसी का ट्रेस बनाएँ।

प्रश्न 4 में void बताता है कि walk कोई मान नहीं लौटाता। return; उसकी वर्तमान कॉल समाप्त करता है। रिकर्सिव कॉल के पहले का printf प्रवेश के समय चलता है; उसके बाद का printf उस कॉल के फिर चलने पर चलता है। प्रश्न 6 कोड पूरा करने का अंश है; शर्त भरे बिना वह संकलित होने वाला प्रोग्राम नहीं है।

प्रश्न 1

पहला हल किया प्रोग्राम जैसा लिखा है, वैसा ही चलाएँ। वह क्या छापता है?

A. 0 6 B. 3 6 C. 3 3 D. 0 0

प्रश्न 2

sum_to(0) कॉल करें। शुरुआती कॉल को गिनते हुए (लौटाया गया मान, sum_to की कुल कॉल) की सही जोड़ी कौन-सी है?

A. (0, 0) B. (1, 1) C. (0, 1) D. (1, 0)

प्रश्न 3

हमारे तार्किक ट्रेस में sum_to(4) के लिए एक ही समय सक्रिय sum_to कॉल की अधिकतम संख्या कितनी है? शुरुआती और आधार स्थिति वाली कॉल गिनें; main तथा लाइब्रेरी कॉल न गिनें।

A. 1 B. 4 C. 10 D. 5

प्रश्न 4

यह प्रोग्राम संख्याएँ किस क्रम में छापता है? अंत की अतिरिक्त स्पेस को अनदेखा करें।

#include <stdio.h>

void walk(int n) {
    if (n == 0) {
        return;
    }
    printf("%d ", n);
    walk(n - 1);
    printf("%d ", n);
}

int main(void) {
    walk(2);
    printf("\n");
    return 0;
}

A. 2 1 1 2 B. 2 1 0 1 2 C. 1 2 2 1 D. 2 2 1 1

प्रश्न 5

यह प्रोग्राम क्या छापता है? हर कॉल का x अलग रखें।

#include <stdio.h>

int layers(int n) {
    int x = 10;
    if (n == 0) {
        return x;
    }
    int below = layers(n - 1);
    x = x + n;
    return x + below;
}

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

A. 12 B. 30 C. 33 D. 36

प्रश्न 6

0 से 6 तक के हर शुरुआती इनपुट के लिए steps को गिनना है कि मान को शून्य या ऋणात्मक बनाने के लिए 2 कितनी बार घटाना पड़ेगा। वर्तमान n शून्य या ऋणात्मक हो तो उसे तुरंत 0 लौटाना चाहिए। रिक्त स्थान में कौन-सी शर्त सही है?

int steps(int n) {
    if (CONDITION) {
        return 0;
    }
    int rest = steps(n - 2);
    return 1 + rest;
}

A. n == 0 B. n <= 0 C. n == 1 D. n < 0

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

उत्तर 1: B

B सही है। लौटे मान क्रमशः 0, 1, 3 और 6 हैं, जबकि main का अपना n = 3 रहता है। A में caller का n गलत तरीके से बदला गया है। C बीच के योग पर रुक जाता है। D caller का मान भी बदलता है और बाकी जोड़ भी छोड़ देता है।

उत्तर 2: C

C सही है: शुरुआती कॉल मौजूद है, n == 0 जाँचती है और कोई रिकर्सिव कॉल किए बिना 0 लौटाती है। A शुरुआती कॉल को नहीं गिनता। B में बिना कारण 1 लौटाया गया है। D दोनों गलतियाँ करता है। आधार स्थिति वाली कॉल भी एक कॉल है।

उत्तर 3: D

D सही है। n = 0 वाली कॉल के लौटने से ठीक पहले सक्रिय पैरामीटर 4, 3, 2, 1 और 0 हैं: कुल पाँच कॉल। A केवल उस समय चल रही कॉल गिनता है। B आधार स्थिति वाली कॉल छोड़ देता है। C लौटाया गया योग है, कॉल की संख्या नहीं। यह तार्किक गणना है, मशीन के स्टैक की माप नहीं।

उत्तर 4: A

A सही है। पहला printf पहले n = 2 पर, फिर n = 1 पर चलता है। n = 0 पर return किसी भी printf से पहले उस कॉल को समाप्त कर देता है। प्रतीक्षा कर रही n = 1 वाली कॉल 1 छापती है; फिर n = 2 वाली कॉल 2 छापती है। B में वह आधार-स्थिति वाला शून्य छापा गया है जिसे कोड छोड़ देता है। C प्रवेश का क्रम उलटता है। D कथनों के क्रम के विरुद्ध बाहरी कॉल को उसकी अंदर वाली कॉल से पहले पूरा करता है।

उत्तर 5: C

C सही है। n = 0 वाली कॉल अपना x = 10 आरंभ करती है और 10 लौटाती है। n = 1 वाली कॉल का अपना x = 10 सुरक्षित रहता है; वह 11 बनता है और 11 + 10 = 21 लौटता है। n = 2 वाली कॉल अपना x, 10 से 12 करती है और 12 + 21 = 33 लौटाती है। A अंदर वाली कॉल से लौटे मान छोड़ देता है। B आधार स्थिति के अलावा बाकी कॉल में x = x + n को अनदेखा करता है। D गलत तरीके से तीनों कॉल में बाहरी कॉल का 12 इस्तेमाल करता है।

उत्तर 6: B

B सही है। steps(3) में पैरामीटर 3, 1 और -1 होते हैं, इसलिए उत्तर 2 है। steps(0) तुरंत 0 लौटाता है। A में विषम शुरुआती इनपुट पर शून्य तक पहुँचा ही नहीं जाता। C शून्य पर नहीं रुकता और 1 पर ज़रूरत से पहले लौटता है। D में n शून्य होने पर एक अनावश्यक चरण चलता है; जैसे steps(0) से 1 लौटेगा। विषम शुरुआती इनपुट पर A वाले रूप और सम शुरुआती इनपुट पर C वाले रूप को न चलाएँ: इन मामलों में रुकने की शर्त नहीं मिलती, इसलिए इन्हें निश्चित आउटपुट वाला अभ्यास न मानें। D दिए गए सभी इनपुट पर रुकता है, लेकिन सम इनपुट के लिए एक चरण ज़्यादा गिनता है।

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

यदि आपने caller का n बदल दिया, तो कॉपी हुए आर्ग्युमेंट वाला भाग दोहराएँ। यदि सबसे अंदर के return पर ही रुक गए, तो प्रतीक्षा कर रहे जोड़ दोबारा बनाएँ। यदि आधार स्थिति वाली कॉल छूट गई, तो शून्य सहित हर प्रवेश की एक पंक्ति लिखें। आउटपुट का क्रम उलझा हो तो हर printf पर निशान लगाएँ कि वह रिकर्सिव कॉल से पहले है या बाद में।

अगले चरण में स्पष्ट सीमा वाले ऐरे पर रिकर्सिव helper का अभ्यास करें। शाखाओं वाला रिकर्शन और संसाधनों का औपचारिक विश्लेषण बाद के पाठों में सीखें; इन छह प्रश्नों में सफलता से उनका पूरा ज्ञान सिद्ध नहीं होता।

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

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