रिकर्शन का समापन और आधार स्थिति का चुनाव

हर स्वीकृत इनपुट के लिए रुकने का तर्क दें

आधार स्थिति तभी काम आती है जब रिकर्सिव चरण उस तक पहुँचें। इस पाठ में आप फ़ंक्शन के स्वीकृत इनपुट बताएँगे, बचे हुए काम का एक गैर-ऋणात्मक पूर्णांक माप चुनेंगे और जाँचेंगे कि हर रिकर्सिव कॉल उस माप को घटाती है। आप यह भी जाँचेंगे कि असुरक्षित व्यंजक का मूल्यांकन होने से पहले फ़ंक्शन लौट जाए।

पहले रिकर्शन: आधार स्थिति और कॉल स्टैक पढ़ें। आपको अलग-अलग कॉल और उनके लौटे मानों का ट्रेस बनाना आना चाहिए। यहाँ हमारा ध्यान प्रत्यक्ष रिकर्शन में रुकने की शर्त चुनने और उसका तर्क देने पर है। रिकर्सिव स्थिति में हर कॉल केवल एक अंदर वाली कॉल करती है। यह पाठ सभी रिकर्सिव एल्गोरिदम नहीं सिखाता और इससे पूरे रिकर्शन में दक्षता सिद्ध नहीं होती।

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

सभी कोड में C11 और सामान्य int मान हैं। हर उदाहरण के स्वीकृत शुरुआती इनपुट बताए गए हैं। दायरे जानबूझकर छोटे हैं, इसलिए दिखाई गई गणनाएँ और परिणाम C में अनिवार्य न्यूनतम int दायरे में भी निरूपण योग्य हैं। इन छोटे ट्रेस के लिए पर्याप्त निष्पादन संसाधन उपलब्ध माने गए हैं। किसी सामान्य सुरक्षित रिकर्शन गहराई का दावा नहीं किया गया है।

गैर-ऋणात्मक पूर्णांकों के लिए n / 2 पूर्णांक भाग है: परिणाम का भिन्नात्मक भाग हट जाता है। इसलिए 13 / 2 का मान 6, 3 / 2 का मान 1, और 1 / 2 तथा 0 / 2 दोनों का मान 0 है। इन उदाहरणों में 0.5 जैसा भिन्न अगली कॉल का int आर्ग्युमेंट नहीं बनता।

प्रमाण से पहले इनपुट की शर्त तय करें

स्वीकृत इनपुट का क्षेत्र (admitted input domain) उन शुरुआती इनपुटों का समूह है जिन पर फ़ंक्शन बताए गए व्यवहार का वादा करता है। halve_rounds के लिए 0 से 31 तक के पूर्णांक स्वीकार करें। इसे गिनना है कि पूर्णांक भाग द्वारा 2 से कितनी बार भाग देने पर मान अधिकतम 1 होगा। इनपुट 0 और 1 पर उत्तर पहले से ही 0 है।

#include <stdio.h>

int halve_rounds(int n) {
    if (n <= 1) {
        return 0;
    }
    int rest = halve_rounds(n / 2);
    return 1 + rest;
}

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

इनपुट की शर्त बताती है कि कौन-सी कॉल स्वीकार्य हैं; वह अपने-आप रन-टाइम जाँच नहीं बन जाती। n <= 1 के कारण यह फ़ंक्शन किसी ऋणात्मक इनपुट पर भी 0 लौटा देगा, लेकिन हमारी शर्त ऋणात्मक शुरुआती मानों के लिए कोई सार्थक गिनती परिभाषित नहीं करती। केवल एक अतिरिक्त इनपुट काम करता दिखे, तो वादे का दायरा न बढ़ाएँ।

शुरुआती इनपुटों और रिकर्सिव कॉल से पहुँची अवस्थाओं में भी अंतर रखें। सहायक फ़ंक्शन को अपने हर पहुँच योग्य अंदर वाले इनपुट पर सही काम करना चाहिए, भले ही वह शुरुआती सूची में न हो। भाग देने वाले उदाहरण में हर अंदर वाला इनपुट 0 से 31 के भीतर है। आगे 2 की छलाँग में 11 भी आएगा, जबकि शुरुआती स्थितियाँ अधिकतम 10 होंगी।

13 से 1 तक हल किया गया ट्रेस

पहली रिकर्सिव कॉल को 13 / 2, यानी 6 मिलता है। हर कॉल का आर्ग्युमेंट और उसके लौटने तक रुका काम लिखें।

प्रोग्राम 3 छापता है। भाग देने के तीन चरण और फ़ंक्शन की चार कॉल हैं; इनमें शुरुआती और आधार स्थिति वाली कॉल शामिल हैं। इस श्रृंखला में दोनों संख्याओं में एक का अंतर है। लौटाया गया मान कॉल की संख्या नहीं है।

सीमांत इनपुट जाँचें: halve_rounds(0) = 0, halve_rounds(1) = 0, halve_rounds(2) = 1 और halve_rounds(3) = 1। इनपुट 31 का क्रम 31 → 15 → 7 → 3 → 1 है, इसलिए उसका परिणाम 4 है।

घटता हुआ गैर-ऋणात्मक माप

समापन माप (termination measure) हर पहुँच योग्य कॉल-अवस्था को एक गैर-ऋणात्मक पूर्णांक देता है। उसे प्रोग्राम में किसी चर के रूप में रखना आवश्यक नहीं है। यहाँ V(n) = n चुनें और ये बातें जाँचें:

1. शुरुआती मान 0 से 31 के भीतर है और हर अगला आर्ग्युमेंट भी इसी दायरे में रहता है।
2. n <= 1 वाली कॉल अंदर कोई नई कॉल किए बिना लौट जाती है।
3. जब भी अंदर वाली कॉल बनती है, n >= 2 होता है। इसलिए 0 <= n / 2 < n है और अंदर वाली कॉल का माप सख्ती से छोटा है।
4. हर कॉल का बाकी काम भी सीमित है और उसकी गणनाएँ परिभाषित हैं। यहाँ लौटते समय छोटी-सी गिनती में 1 जोड़ा जाता है।

गैर-ऋणात्मक पूर्णांक हमेशा सख्ती से घटता नहीं रह सकता। इसलिए रिकर्सिव कॉल की श्रृंखला अनंत समय तक आगे नहीं बढ़ सकती। वह लौटने वाली स्थिति तक पहुँचती है और फिर प्रतीक्षा कर रही सीमित संख्या की कॉल भी लौट सकती हैं। माप का ठीक शून्य होना आवश्यक नहीं था: यहाँ आधार स्थिति माप 1 पर भी रोकती है।

“छोटा होता है” को स्पष्ट करना ज़रूरी है। नीचे की सीमा के बिना घटता पूर्णांक पर्याप्त नहीं है: गणितीय क्रम 1, -2, -5, ... लगातार घट सकता है। गैर-ऋणात्मक माप का अपरिवर्तित रहना भी पर्याप्त नहीं है। यह पूर्णांकों वाला तर्क मनमानी वास्तविक संख्याओं पर लागू नहीं होता: 1, 1/2, 1/4, ... शून्य तक पहुँचे बिना हमेशा घट सकता है।

पैरामीटर बढ़ सकता है जबकि बचा हुआ काम घटे

मानें कि शुरुआती स्थिति 0 से 10 तक का पूर्णांक है। हर छलाँग में 2 जुड़ता है। हमें 10 तक पहुँचने या उसे पार करने के लिए आवश्यक छलाँगों की संख्या चाहिए।

int hops_to_ten(int pos) {
    if (pos >= 10) {
        return 0;
    }
    int rest = hops_to_ten(pos + 2);
    return 1 + rest;
}

hops_to_ten(7) में स्थितियाँ 7 → 9 → 11 हैं, इसलिए उत्तर 2 है। पैरामीटर बढ़ रहा है। उपयुक्त माप अभी तय की जाने वाली गैर-ऋणात्मक दूरी है: V(pos) = max(10 - pos, 0)। यहाँ max(a, b) बड़े मान के लिए गणितीय संकेत है; कोई C फ़ंक्शन कॉल करना आवश्यक नहीं है।

पहुँच योग्य स्थितियाँ 0 से 11 के भीतर हैं। pos <= 8 वाली रिकर्सिव अवस्था में माप 2 घटता है। pos = 9 पर अंदर वाली कॉल स्थिति 11 तक जाती है और माप 1 से 0 हो जाता है। स्थिति 10 या 11 पर कॉल लौटती है। इसलिए हर अंदर वाली कॉल एक गैर-ऋणात्मक पूर्णांक माप को सख्ती से घटाती है, भले ही pos बढ़ रहा हो। इस छोटे पहुँच योग्य दायरे में जोड़ भी सुरक्षित है।

यदि शर्त केवल pos == 10 होती, तो विषम स्थितियों का रास्ता 7 → 9 → 11 → ... लक्ष्य को पार कर देता। सामान्य पूर्णांक गणना में वह बाद में 10 पर नहीं आता। उस दोषपूर्ण रूप को न चलाएँ: C में आगे चलते रहने से संसाधन समाप्त हो सकते हैं या अंततः signed integer overflow हो सकता है। overflow कोई मान्य रुकने की शर्त या निश्चित आउटपुट नहीं देता।

जब इनपुट की शर्त और चरण ठीक लक्ष्य तक पहुँचने की गारंटी दें, तब बराबरी वाली आधार स्थिति सही हो सकती है। 3 के गैर-ऋणात्मक गुणज से बार-बार 3 घटाने पर अंततः 0 आता है। वही बराबरी की शर्त हर गैर-ऋणात्मक पूर्णांक के लिए उचित नहीं है। इनपुट का क्षेत्र, रिकर्सिव चरण, रुकने की शर्त और लौटे परिणाम का अर्थ साथ में चुनें। केवल == को <= या >= में बदलना हर समस्या का समाधान नहीं है।

पूर्णांक भाग में दो सीमांत मान महत्वपूर्ण हैं

धनात्मक शुरुआती इनपुटों के लिए n == 1 की आधार स्थिति के साथ 2 से भाग देने का तर्क दिया जा सकता है। शून्य स्वीकार करते ही वह प्रमाण पूरे इनपुट क्षेत्र को नहीं ढकता: 0 / 2 फिर 0 है, इसलिए शून्य पर बिना रोक वाली कॉल उसी अवस्था को दोहराती है। वह 1 की ओर प्रगति नहीं करती।

हमारी गिनती में सही आधार शर्त n <= 1 है क्योंकि 0 और 1 दोनों के लिए शून्य चरण चाहिए। n == 0 की आधार शर्त भी स्वीकृत गैर-ऋणात्मक इनपुटों पर अंततः रोक देगी, लेकिन 1 पर एक अनावश्यक अंतिम भाग गिनेगी। उदाहरण के लिए, इनपुट 1 पर वह निर्धारित 0 के बजाय 1 लौटाएगी। रुकना और सही उत्तर देना अलग-अलग ज़िम्मेदारियाँ हैं।

जिस व्यंजक को सुरक्षित करना हो उससे पहले रोक लगाएँ

अगले सहायक फ़ंक्शन के शुरुआती इनपुट 0 से 31 तक के पूर्णांक हैं। 0 और 1 पर परिणाम 0 परिभाषित करें। हर बड़े मान पर पूर्णांक भागफल 12 / (n - 1) को आधा किए हुए इनपुट की अंदर वाली कॉल के स्कोर में जोड़ें।

int guarded_score(int n) {
    if (n <= 1) {
        return 0;
    }
    int part = 12 / (n - 1);
    int rest = guarded_score(n / 2);
    return part + rest;
}

n = 1 पर part की घोषणा और आरंभीकरण से पहले return चल जाता है। इसलिए 12 / (n - 1) का मूल्यांकन नहीं होता और शून्य से भाग नहीं दिया जाता। हर रिकर्सिव अवस्था में n >= 2 है, इसलिए भाजक (denominator) कम-से-कम 1 है, अंदर वाला इनपुट छोटा है और यही तर्क आगे भी लागू होता है। guarded_score(6) में पहले 12 / 5 = 2, फिर 12 / 2 = 6 और अंत में आधार परिणाम 0 मिलता है। कुल स्कोर 8 है।

यदि int part = 12 / (n - 1); को रोकने वाली शर्त से ऊपर रखा जाए, तो इनपुट 1 पर लौटने से पहले ही खतरनाक व्यंजक का मूल्यांकन होगा। बाद में की गई आधार-स्थिति की जाँच पहले हो चुके शून्य से भाग को ठीक नहीं कर सकती। पास की टिप्पणी में “आधार स्थिति” लिख देने से compiler किसी अमान्य C व्यंजक को सुरक्षित नहीं बनाता।

यहाँ आधा होने वाला वही माप सिद्ध करता है कि रिकर्सिव श्रृंखला सीमित है। उससे अलग हमने भाग, घटाव और लौटते समय की गणनाएँ जाँची हैं। केवल समापन का तर्क यह सिद्ध नहीं करता कि C का निष्पादन परिभाषित है या परिणाम दिए गए काम के अनुसार है।

एक सटीक उपमा

कल्पना करें कि एक काउंटर बताता है कि निकास तक पहुँचने के लिए फ़र्श के कितने निशान बाकी हैं। एक बार में दो निशान चलने पर निकास पार भी हो सकता है, इसलिए “निकास पर या उससे आगे” सही रुकने की शर्त हो सकती है। वर्तमान निशान की संख्या बढ़ सकती है जबकि बची दूरी घटती है। काउंटर शून्य होते ही आप उस उपकरण को चलाने से पहले निकल जाते हैं जो केवल अधूरे काम के लिए था।

यह उपमा गैर-ऋणात्मक पूर्णांक माप और पहले लौटने को समझाती है। इसका अर्थ यह नहीं कि प्रोग्राम वास्तव में माप निकालता है, हर चरण उसे केवल एक घटाता है या वास्तविक मशीन में प्रतीक्षा कर रही कॉल के लिए असीमित जगह होती है।

मुख्य बातें समापन का तर्क कैसे दें

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

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

हर प्रश्न में ठीक एक उत्तर चुनें। प्रत्येक में चार विकल्प हैं। जहाँ पूरा संदर्भ नहीं दिया है, वहाँ कोड फ़ंक्शन के अंश हैं, स्वतंत्र प्रोग्राम नहीं; प्रश्न 3 पूरा प्रोग्राम है। अमान्य विकल्पों को चलाए बिना उनका विश्लेषण करें।

प्रश्न 1

दिए गए किस एक शुरुआती इनपुट-समूह के हर मान से बार-बार 3 घटाने पर n == 0 तक पहुँचा जाता है? आर्ग्युमेंट के क्रम से तर्क दें; असफल इनपुट न चलाएँ। सूची के सभी मान int में निरूपित गणितीय पूर्णांक हैं।

int groups_of_three(int n) {
    if (n == 0) {
        return 0;
    }
    int rest = groups_of_three(n - 3);
    return 1 + rest;
}

A. 0 से 9 तक हर पूर्णांक

B. केवल 0, 3, 6 और 9

C. केवल 1, 4 और 7

D. -3 से 0 तक हर पूर्णांक

प्रश्न 2

0 से 10 तक की शुरुआती स्थितियों वाले hops_to_ten के लिए सभी पहुँच योग्य कॉल पर कौन-सा समापन तर्क सही है?

int hops_to_ten(int pos) {
    if (pos >= 10) {
        return 0;
    }
    int rest = hops_to_ten(pos + 2);
    return 1 + rest;
}

A. max(10 - pos, 0) गैर-ऋणात्मक पूर्णांक है और हर अंदर वाली कॉल पर सख्ती से घटता है।

B. pos गैर-ऋणात्मक पूर्णांक है और हर अंदर वाली कॉल पर सख्ती से घटता है।

C. रिकर्सिव चरण कैसा भी हो, फ़ंक्शन में कहीं return होना पर्याप्त है।

D. हर पहुँच योग्य कॉल में 10 - pos गैर-ऋणात्मक रहता है, pos = 11 वाली कॉल में भी।

प्रश्न 3

यह पूरा प्रोग्राम क्या छापता है?

#include <stdio.h>

int halve_rounds(int n) {
    if (n <= 1) {
        return 0;
    }
    int rest = halve_rounds(n / 2);
    return 1 + rest;
}

int main(void) {
    int a = halve_rounds(0);
    int b = halve_rounds(1);
    int c = halve_rounds(2);
    printf("%d %d %d\n", a, b, c);
    return 0;
}

A. 1 1 2

B. 0 1 2

C. 0 0 1

D. 0 0 0

प्रश्न 4

एक विद्यार्थी भाग देने वाले फ़ंक्शन की आधार शर्त n == 1 कर देता है और अब शून्य भी स्वीकार करता है। faulty_halves(0) की समस्या कौन-सा कथन सही बताता है? उसे न चलाएँ।

/* Reason about this fragment; do not run it at n = 0. */
int faulty_halves(int n) {
    if (n == 1) {
        return 0;
    }
    return 1 + faulty_halves(n / 2);
}

A. अगला आर्ग्युमेंट 0.5 है, जिसे ऊपर पूर्णांकित करने पर 1 मिलता है।

B. अगला आर्ग्युमेंट 0 ही रहता है, इसलिए आधार जाँच असत्य रहती है और सख्त प्रगति नहीं होती।

C. पूर्णांक भाग का परिणाम शून्य होते ही फ़ंक्शन अपने-आप लौट जाता है।

D. हर रिकर्सिव कॉल n को ठीक 1 घटाती है, इसलिए शून्य जल्द ही एक हो जाता है।

प्रश्न 5

0 से 8 तक के शुरुआती पूर्णांक स्वीकार करें। अपेक्षित स्कोर 0 और 1 पर 0 है। n >= 2 पर यह पूर्णांक भाग से निकला 12 / (n - 1), और n / 2 का स्कोर जोड़कर मिलता है। कौन-सा रूप हर स्वीकृत इनपुट पर परिभाषित है और यह नियम पूरा करता है? गलत विकल्पों को चलाए बिना जाँचें।

A.

int guarded_score(int n) {
    if (n <= 1) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

B.

int guarded_score(int n) {
    int part = 12 / (n - 1);
    if (n <= 1) { return 0; }
    return part + guarded_score(n / 2);
}

C.

int guarded_score(int n) {
    if (n == 0) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

D.

int guarded_score(int n) {
    if (n <= 2) { return 0; }
    int part = 12 / (n - 1);
    return part + guarded_score(n / 2);
}

प्रश्न 6

इस पाठ का भाग देने वाला प्रमाण और परीक्षण बताए गए छोटे इनपुट क्षेत्र को ढकते हैं। कौन-सा निष्कर्ष उचित है?

A. केवल कुछ सफल रन सिद्ध करते हैं कि हर संभव signed int इनपुट अपेक्षित शर्त पूरी करता है।

B. समापन माप से, रिकर्सिव नियम या आधार मान जाँचे बिना, हर लौटे परिणाम की शुद्धता भी सिद्ध हो जाती है।

C. गैर-ऋणात्मक पूर्णांक माप घटते ही वास्तविक मशीन को मनमानी संख्या में सक्रिय कॉल संभालनी ही होगी।

D. बताए गए इनपुट क्षेत्र, परिभाषित गणनाओं और इन छोटे मामलों के लिए पर्याप्त संसाधनों के साथ घटता माप अंतहीन कॉल-श्रृंखला को असंभव करता है; मनमानी गहराई पर संसाधन-सुरक्षा अलग विषय है।

उत्तर और हर विकल्प की व्याख्या

उत्तर 1 B

• A. गलत। इस समूह में 1 है, जिसका अगला आर्ग्युमेंट -2 होगा। 3 घटाते रहने से यह गणितीय क्रम वापस शून्य पर नहीं आएगा।

• B. सही। ये 3 के गैर-ऋणात्मक गुणज हैं। हर धनात्मक अवस्था में 3 घटने के बाद भी मान 3 का गैर-ऋणात्मक गुणज रहता है और फिर शून्य तक पहुँचता है।

• C. गलत। इन सभी मानों को 3 से भाग देने पर शेष 1 है। इनके रास्ते 1, फिर -2 तक आते हैं और शून्य को छोड़ देते हैं।

• D. गलत। शून्य पर कॉल लौटती है, लेकिन सूची का हर ऋणात्मक शुरुआती मान शून्य से और नीचे जाता है। एक सफल सदस्य से पूरे इनपुट क्षेत्र का तर्क नहीं मिलता।

उत्तर 2 A

• A. सही। अधिकतम 8 वाली रिकर्सिव स्थिति पर माप 2 घटता है; 9 से 11 जाने पर 1 से 0 होता है। कम-से-कम 10 वाली स्थिति पर कॉल लौटती है।

• B. गलत। अंदर वाला आर्ग्युमेंट pos + 2 है, इसलिए pos बढ़ता है। घटने वाला माप बची हुई दूरी है।

• C. गलत। return तक पहुँचना भी ज़रूरी है। केवल 10 से बराबरी जाँचने पर विषम स्थितियों का रास्ता उसे छोड़ देगा।

• D. गलत। स्थिति 11 पर इस व्यंजक का मान -1 है। शून्य के साथ अधिकतम लेने पर हर पहुँच योग्य अवस्था में दावा किया गया गैर-ऋणात्मक माप मिलता है।

उत्तर 3 C

• A. गलत। ये तीनों श्रृंखलाओं की कॉल-संख्याएँ हैं, लौटाई गई भाग देने के चरणों की संख्याएँ नहीं।

• B. गलत। इसमें 1 से 0 तक का अंतिम चरण भी गिना गया है। वास्तविक शर्त 1 पर तुरंत लौटा देती है।

• C. सही। इनपुट 0 और 1 को कोई चरण नहीं चाहिए। इनपुट 2 में 2 से 1 तक एक चरण बनता है और 1 लौटता है।

• D. गलत। इनपुट 2 पर n <= 1 सत्य नहीं है। उसकी कॉल को एक रिकर्सिव चरण बनाकर गिनना पड़ता है।

उत्तर 4 B

• A. गलत। C11 के पूर्णांक भाग में 0 / 2 का मान 0 है। न कोई भिन्नात्मक आर्ग्युमेंट बनता है, न ऊपर की ओर पूर्णांकन होता है।

• B. सही। तार्किक आर्ग्युमेंट क्रम 0, 0, 0 आदि है। यह सीमित चरणों में लौटने वाला मामला नहीं है। संसाधन विफलता या compiler के रूपांतरण को आधार स्थिति तक पहुँचना न मानें।

• C. गलत। शून्य मान निकलने से return कथन नहीं चलता। कोड यह जाँचता है कि n का मान 1 है या नहीं।

• D. गलत। 2 से भाग देना, 1 घटाना नहीं है। शून्य से 1 घटाने पर भी धनात्मक एक की ओर प्रगति नहीं होगी।

उत्तर 5 A

• A. सही। 0 और 1 पर भाग देने से पहले रोकने वाली शर्त लौटा देती है। हर अन्य पहुँच योग्य अवस्था में भाजक धनात्मक है और रिकर्सिव चरण निर्धारित स्कोर का नियम पूरा करता है।

• B. गलत। इनपुट 1 पर शर्त जाँचने से पहले part का आरंभीकरण शून्य से भाग द्वारा होता है। बाद में लौटना उस अपरिभाषित व्यवहार को ठीक नहीं करता।

• C. गलत। इनपुट 1 पर n == 0 असत्य है और भाजक शून्य है। रोकने वाली शर्त एक ज़रूरी सीमांत मामला छोड़ देती है।

• D. गलत। यह रूप इनपुट 2 पर 0 लौटाता है, लेकिन अपेक्षित परिणाम 12 / 1 + score(1) = 12 है। यह सुरक्षित रूप से रुकता है, फिर भी गलत स्कोर लौटाता है।

उत्तर 6 D

• A. गलत। चुने हुए इनपुटों के परीक्षण से शर्त सभी signed integer तक नहीं फैलती। दावा जितना बड़ा हो, इनपुट क्षेत्र और तर्क को उतना ही ढकना चाहिए।

• B. गलत। उदाहरण के लिए, भाग देने वाली आधार स्थिति का लौटाया मान 0 से 7 कर दें, तो समापन बना रहेगा लेकिन अपेक्षित गिनती गलत हो जाएगी।

• C. गलत। आवश्यक कॉल की संख्या सीमित होने पर भी वह वास्तविक implementation के उपलब्ध संसाधनों से अधिक हो सकती है। माप भौतिक स्मृति की गारंटी नहीं है।

• D. सही। बताई गई शर्तों पर प्रमाण तार्किक प्रगति और सीमित अवरोह देता है। वह असीमित संसाधनों का वादा नहीं करता और लौटे परिणाम के अर्थ की अलग जाँच का स्थान नहीं लेता।

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

किसी नए रिकर्सिव सहायक फ़ंक्शन का ट्रेस बनाने से पहले तीन बातें लिखें: “ये शुरुआती इनपुट स्वीकार हैं”, “ये सीमांत अवस्थाएँ पहुँच योग्य हैं” और “यह गैर-ऋणात्मक पूर्णांक हर रिकर्सिव कॉल पर घटता है”। उसके बाद आधार परिणाम, गणनाओं की सुरक्षा और लौटते समय होने वाला काम अलग से जाँचें।

यदि आपने केवल बराबरी की शर्त चुनी है, तो ऐसा इनपुट आज़माकर सोचें जो लक्ष्य को पार कर सकता हो। भाग देने वाले उदाहरण में 0, 1, 2 और एक विषम इनपुट जाँचें। किसी खतरनाक व्यंजक के पास रोकने वाली शर्त हो, तो कथनों का क्रम देखकर पूछें कि क्या return पहले चलता है। ये आदतें सीमित ऐरे पर रिकर्शन सीखने की तैयारी हैं; वे आगे आने वाले शाखाओं वाले रिकर्शन, पुनरावृत्ति संबंधों या संसाधन जटिलता के अध्ययन का विकल्प नहीं हैं।

स्रोत और दायरे की टिप्पणी

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