रिकर्शन: 12 प्रश्नों की सीखने की समीक्षा

इस समीक्षा से अगला सुधार चुनें

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

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

साझा नियम

• C11 लें। हर प्रश्न में छोटे स्वीकृत इनपुट का दायरा या सटीक इनपुट दिया है; उससे मनमाने signed integer या रिकर्शन की गहराई का निष्कर्ष न निकालें।
• हर सामान्य पैरामीटर/स्थानीय चर अपनी कॉल का है। ऐरे-पैरामीटर वाले प्रश्न caller का मौजूदा भंडारण इस्तेमाल करते हैं; चुनी गई लंबाई ऐरे को न कॉपी करती है, न उसका आकार बदलती है।
• n लंबाई के शुरुआती भाग में सूचकांक 0 से n - 1 तक आते हैं। n = 0 पर वह खाली है। दिखाए गए सभी वास्तविक ऐरे की क्षमता धनात्मक है; “खाली शुरुआती भाग” का अर्थ शून्य लंबाई का C ऐरे घोषित करना नहीं।
• const int a[] उस पैरामीटर के माध्यम से तत्व बदलने से रोकता है। वह नया ऐरे नहीं बनाता। प्रश्न 12 में जानबूझकर लिखने योग्य ऐरे पैरामीटर है।
• कॉल गिनने वाले प्रश्नों में बताए गए helper की शुरुआती और आधार स्थिति वाली कॉल जोड़ें। main और लाइब्रेरी कॉल छोड़ें। प्रतीक्षा कर रहे caller को उसके लौटने तक सक्रिय गिनें।
• अधिकतम सक्रिय फ़्रेम तार्किक कॉल-रिकॉर्ड हैं, स्टैक की मापी हुई बाइट या कंपाइलर के भौतिक भंडारण का वादा नहीं। अलग कथनों में लिखी अंदर वाली कॉल दिखाए क्रम से चलती हैं; पूरी हो चुकी साथ की शाखा सक्रिय नहीं रहती।
• फ़ंक्शन अंश को प्रोग्राम की तरह चलाने के लिए वैध caller और ज़रूरी headers जोड़ें। प्रश्न 1 और 12 पूरे प्रोग्राम हैं। प्रश्न 8 और प्रश्न 3 के असफल विकल्पों में अपरिभाषित या न रुकने वाला कोड चलाए बिना विश्लेषण करें।

प्रश्न

प्रश्न 1

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

#include <stdio.h>

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

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

A. 3 2

B. 0 2

C. 3 5

D. 0 5

प्रश्न 2

0 से 26 तक के शुरुआती इनपुट के लिए reduce गिनता है कि मान अधिकतम 2 होने तक 3 से कितनी बार भाग देना पड़ता है। reduce(26) क्या लौटाता है?

int reduce(int n) {
    if (n <= 2) { return 0; }
    int child = reduce(n / 3);
    return 1 + child;
}

A. 0

B. 1

C. 2

D. 3

प्रश्न 3

किस प्रस्तावित शुरुआती इनपुट-समूह के हर सदस्य से बराबरी वाली आधार स्थिति तक पहुँचना निश्चित है? आर्ग्युमेंट के क्रम का विश्लेषण करें; असफल इनपुट न चलाएँ।

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

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

B. केवल 0, 4, 8 और 12

C. केवल 2, 6 और 10

D. केवल -4 और 0

प्रश्न 4

0 से 3 तक के शुरुआती इनपुट में blend(3) क्या मान लौटाता है?

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

A. 26

B. 41

C. 42

D. 53

प्रश्न 5

0 से 4 तक के शुरुआती इनपुट में zig(3) क्या लौटाता है? अंदर वाली कॉल के बाद की जाँच में इसी caller का n इस्तेमाल होता है।

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

A. 3

B. 5

C. 7

D. 9

प्रश्न 6

int a[4] = {2, 1, 3, 8} दिया है। weighted(a, 3) क्या लौटाता है? 0 <= n <= 4 स्वीकार करें; हर चुने गए तत्व को उसकी 1 से शुरू होने वाली स्थिति से गुणा किया जाता है।

int weighted(const int a[], int n) {
    if (n == 0) { return 0; }
    int child = weighted(a, n - 1);
    return child + n * a[n - 1];
}

A. 7

B. 13

C. 21

D. 45

प्रश्न 7

int a[4] = {2, 1, 2, 5} दिया है। (count_equal(a, 0, 2), count_equal(a, 3, 2)) की सही जोड़ी कौन-सी है? 0 <= n <= 4 स्वीकार करें।

int count_equal(const int a[], int n, int target) {
    if (n == 0) { return 0; }
    int child = count_equal(a, n - 1, target);
    if (a[n - 1] == target) { return child + 1; }
    return child;
}

A. (1, 2)

B. (0, 3)

C. (4, 2)

D. (0, 2)

प्रश्न 8

int a[3] = {4, 7, 9} के लिए bad_sum(a, 3) की कौन-सी जाँच सही है? यह दोषपूर्ण कॉल न चलाएँ।

/* Analyze this faulty fragment; do not run bad_sum(a, 3). */
int bad_sum(const int a[], int n) {
    if (n == 0) { return 0; }
    int last = a[n];
    int child = bad_sum(a, n - 1);
    return last + child;
}

A. यह अवश्य 20 लौटाएगा क्योंकि भंडारित तीनों तत्व जुड़ते हैं।

B. पहली गैर-आधार कॉल में वास्तविक ऐरे के बाहर a[3] पढ़ा जाता है; इस कोड का कोई निश्चित C आउटपुट नहीं बताया जा सकता।

C. n == 0 वाली शर्त हर ऐरे-पढ़ने को सुरक्षित बनाती है।

D. यह अवश्य 0 लौटाएगा क्योंकि a[3] अपने-आप शून्य से आरंभ होता है।

प्रश्न 9

0 से 5 तक के शुरुआती इनपुट में jumps(5) देखें। (लौटाया गया मान, jumps की कुल कॉल, एक समय पर अधिकतम सक्रिय jumps कॉल) का सही त्रिक कौन-सा है? शुरुआती और आधार कॉल गिनें; main तथा लाइब्रेरी कॉल छोड़ें।

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

A. (3, 4, 4)

B. (4, 4, 4)

C. (3, 3, 3)

D. (3, 7, 4)

प्रश्न 10

0 से 3 तक के अनुमत शुरुआती इनपुट में leaves(2) देखें। (लौटाया गया मान, leaves की कुल कॉल, एक समय पर अधिकतम सक्रिय leaves कॉल) का सही त्रिक कौन-सा है? तार्किक निष्पादन गिनें; शुरुआती/आधार कॉल जोड़ें और main/लाइब्रेरी कॉल छोड़ें।

int leaves(int n) {
    if (n == 0) { return 1; }
    int left = leaves(n - 1);
    int right = leaves(n - 1);
    return left + right;
}

A. (4, 4, 3)

B. (4, 7, 7)

C. (7, 7, 3)

D. (4, 7, 3)

प्रश्न 11

0 से 4 तक के अनुमत शुरुआती इनपुट में mixed(3) के लिए (mixed की कुल कॉल, अधिकतम सक्रिय mixed कॉल) की सही जोड़ी कौन-सी है? प्रश्न 10 वाला ही तार्किक गिनती-नियम लें।

int mixed(int n) {
    if (n <= 1) { return 1; }
    int first = mixed(n - 1);
    int second = mixed(n - 2);
    return first + second;
}

A. (3, 3)

B. (5, 3)

C. (5, 5)

D. (7, 3)

प्रश्न 12

यह पूरा प्रोग्राम क्या छापता है? ऐरे की क्षमता 3 है और चुनी गई लंबाई 0 से 3 तक हो सकती है। void और return; का अर्थ है कि कोई संख्यात्मक मान नहीं लौटाया जाता।

#include <stdio.h>

void raise_prefix(int a[], int n) {
    if (n == 0) { return; }
    raise_prefix(a, n - 1);
    a[n - 1] = a[n - 1] + n;
}

int main(void) {
    int a[3] = {3, 3, 3};
    raise_prefix(a, 2);
    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

A. 4 5 6

B. 3 3 3

C. 4 5 3

D. 5 4 3

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

उत्तर 1: A

• A. सही। आधार मान 5 से शुरू करके प्रतीक्षा कर रही कॉल 4, 3 और 2 लौटाती हैं। main का अपना n = 3 रहता है।

• B. गलत। परिणाम 2 सही है, लेकिन रिकर्सिव पैरामीटर के मान main के n को नहीं बदलते।

• C. गलत। इसमें main का n सही रखा गया है, लेकिन प्रतीक्षा कर रहे तीन घटाव छोड़ दिए गए हैं।

• D. गलत। इसमें caller का n भी बदला गया है और बाकी गणना भी छोड़ दी गई है।

उत्तर 2: C

• A. गलत। शुरुआती 26 पर n <= 2 सत्य नहीं है, इसलिए कम-से-कम एक रिकर्सिव चरण चाहिए।

• B. गलत। पहली अंदर वाली कॉल का इनपुट 8 है, जो अभी भी 2 से बड़ा है; एक और चरण चाहिए।

• C. सही। पूर्णांक भाग से 26 → 8 → 2 मिलता है। दो बार भाग देना गिना जाता है; आधार स्थिति वाली कॉल 0 लौटाती है।

• D. गलत। तीन कॉल होती हैं, लेकिन लौटाई गई गिनती भाग देने के दो चरणों की है। 2 पर भाग नहीं दिया जाता।

उत्तर 3: B

• A. गलत। इसमें 1 शामिल है; गणितीय क्रम 1, -3, -7, … कभी शून्य तक नहीं पहुँचता।

• B. सही। 4 का गैर-ऋणात्मक गुणज घटते हुए भी 4 का गैर-ऋणात्मक गुणज रहता है और शून्य तक पहुँचता है।

• C. गलत। ये रास्ते 2 और फिर -2 तक आते हैं, इसलिए शून्य छूट जाता है। बराबरी की जाँच के लिए ठीक उसी मान तक पहुँचना चाहिए।

• D. गलत। शून्य पर कॉल लौटती है, लेकिन -4 से -8 और उससे नीचे जाते हैं। एक सफल इनपुट से पूरा समूह सही नहीं हो जाता।

उत्तर 4: B

• A. गलत। यह 3 * 3 * 3 - 1 है। इसमें आधार मान 2 छोड़ दिया है और हर गैर-आधार वापसी पर घटाने की जगह केवल एक बार घटाया है।

• B. सही। आर्ग्युमेंट 0, 1, 2, 3 से लौटे मान 2, 5, 14, 41 हैं। अंतिम गणना 3 * 14 - 1 है।

• C. गलत। इसमें 14 को 3 से गुणा किया है, लेकिन अंत का 1 घटाना छोड़ दिया है।

• D. गलत। इसमें 2 * 3 * 3 * 3 - 1 निकाला है और केवल एक बार घटाया है। कोड आधार स्थिति के अलावा हर वापसी पर 1 घटाता है।

उत्तर 5: C

• A. गलत। यह zig(2) का मान है; प्रतीक्षा कर रही n = 3 वाली कॉल का काम बाकी है।

• B. गलत। इसमें zig(2) = 3 में 2 ऐसे जोड़ा है मानो n = 3 वाला caller सम हो। वह विषम है।

• C. सही। आधार स्थिति 0 लौटाती है; n = 1 से 1, n = 2 से 3 और n = 3 से 2 * 3 + 1 = 7 लौटता है।

• D. गलत। विषम शाखा लौट चुकी होने के बाद फिर 2 जोड़ दिया गया है। चल चुका return उस कॉल को समाप्त करता है।

उत्तर 6: B

• A. गलत। यह 0 से शुरू भार देने पर 0 * 2 + 1 * 1 + 2 * 3 का योग है। कोड में भार 1, 2 और 3 हैं।

• B. सही। चुने गए शुरुआती भाग का योगदान 1 * 2 + 2 * 1 + 3 * 3 = 13 है। सूचकांक 3 वाला तत्व नहीं चुना गया है।

• C. गलत। इसमें कोड का पालन किए बिना सही शुरुआती-भाग के परिणाम में न चुना गया 8 जोड़ दिया है।

• D. गलत। यह चारों तत्वों का भारित योग है। कॉल में केवल तीन तत्व चुने गए हैं।

उत्तर 7: D

• A. गलत। चुना गया खाली शुरुआती भाग कोई मेल नहीं रखता, भले ही उसके बाहर ऐरे का भंडारण मौजूद हो।

• B. गलत। चुने गए तीन मान 2, 1 और 2 हैं। लक्ष्य के बराबर केवल दो हैं; तत्वों की संख्या मेल की संख्या नहीं है।

• C. गलत। ऐरे की क्षमता 4, चुने गए खाली शुरुआती भाग का उत्तर नहीं है।

• D. सही। n = 0 पर कोई तत्व पढ़ने से पहले 0 लौटता है। n = 3 पर सूचकांक 0 और 2 लक्ष्य से मेल खाते हैं, इसलिए 2 मिलता है।

उत्तर 8: B

• A. गलत। इच्छित योग यह तय नहीं करता कि सीमा से बाहर C ऐरे पढ़ने पर क्या होगा।

• B. सही। वैध सूचकांक 0, 1 और 2 हैं। n = 3 पर a[n] पढ़ना पहले ही अमान्य है; आखिरी चुना तत्व a[n - 1] होता।

• C. गलत। यह शर्त खाली मामला सँभालती है, धनात्मक लंबाई में इस्तेमाल गलत सूचकांक को नहीं।

• D. गलत। ऐरे में चौथा तत्व है ही नहीं। छूटे initializer के नियम अतिरिक्त तत्व नहीं बनाते।

उत्तर 9: A

• A. सही। आर्ग्युमेंट शृंखला 5, 3, 1, -1 है। आधार कॉल के लौटने से ठीक पहले चार कॉल साथ सक्रिय हैं; तीन गैर-आधार कॉल 1-1 जोड़ती हैं।

• B. गलत। आधार स्थिति 0 लौटाती है और 1 नहीं जोड़ती, इसलिए लौटा मान 3 है, चार कॉल की गिनती नहीं।

• C. गलत। इसमें -1 वाली आधार कॉल दोनों कॉल-गिनतियों से छूट गई है।

• D. गलत। हर गैर-आधार कॉल की केवल एक अंदर वाली कॉल है, इसलिए कोई अतिरिक्त साथ की शाखा नहीं है। सात गिनने पर काल्पनिक वृक्ष बना दिया गया है।

उत्तर 10: D

• A. गलत। चार आधार स्थिति वाले पत्तों की संख्या है, सभी कॉल की नहीं। मूल कॉल और दो गैर-आधार अंदर वाली कॉल भी गिननी हैं।

• B. गलत। समय के साथ सात कॉल होती हैं, लेकिन साथ की शाखाएँ क्रम से चलती हैं; सभी एक साथ सक्रिय नहीं होतीं।

• C. गलत। हर आधार कॉल 1 लौटाती है और वही मान जुड़ते हैं। लौटा मान 4 है, कुल कॉल-संख्या 7 नहीं।

• D. सही। एक मूल कॉल, n = 1 की दो कॉल और n = 0 की चार कॉल हैं: कुल सात। सबसे लंबा सक्रिय रास्ता 2 → 1 → 0 है: तीन कॉल। चार आधार मानों का योग 4 है।

उत्तर 11: B

• A. गलत। यहाँ तीन लौटा मान भी है और अधिकतम गहराई भी, लेकिन कुल कॉल में n = 2 की दोनों अंदर वाली कॉल और अंत की n = 1 वाली दूसरी शाखा भी आती है।

• B. सही। प्रवेश के क्रम में कॉल हैं: 3, 2, 1, 0, 1। कुल पाँच कॉल होती हैं और सबसे लंबा सक्रिय रास्ता 3 → 2 → 1 (या 0) है, जिसमें तीन सक्रिय कॉल हैं।

• C. गलत। दूसरी अंदर वाली कॉल शुरू होने से पहले पहली वाली पूरी हो जाती है। सभी कॉल एक साथ सक्रिय नहीं रहतीं।

• D. गलत। n = 3 की दूसरी अंदर वाली कॉल n = 1 है, जो तुरंत लौटती है। वह दूसरा n = 2 वाला उपवृक्ष नहीं है।

उत्तर 12: C

• A. गलत। इसमें न चुना गया तीसरा तत्व भी बदल दिया है। शुरुआती चुनी गई लंबाई 2 है, क्षमता 3 नहीं।

• B. गलत। ऐरे के तत्व caller के साझा भंडारण में हैं; पूरे ऐरे की कॉपी नहीं बनती। a के माध्यम से वैध लिखाई caller को दिखने वाले तत्व बदलती है।

• C. सही। खाली कॉल लौटने के बाद n = 1 पर a[0] में 1 जुड़ता है, फिर n = 2 पर a[1] में 2 जुड़ता है। a[2] नहीं बदलता, इसलिए 4 5 3 मिलता है।

• D. गलत। इसमें पहले तत्व में 2 और दूसरे में 1 जोड़ा है, जिससे n = 1 और n = 2 के बढ़ोतरी-मान उलट गए हैं। लौटने वाली हर कॉल a[n - 1] में अपना n जोड़ती है।

परिणाम से तय करें कि कौन-सा पाठ दोहराना है

• प्रश्न 1, 4 और 5: हर caller का अलग रिकॉर्ड रखें और अंदर वाली कॉल का लौटा मान रखने से पहले ठीक बाकी गणना लिखें।
• प्रश्न 2 और 3: स्वीकार्य इनपुट का क्षेत्र बताएँ, सीमा जाँचें और प्रगति समझाएँ; केवल return दिख जाना पर्याप्त नहीं।
• प्रश्न 6, 7, 8 और 12: वास्तविक क्षमता, चुनी गई लंबाई और आखिरी वैध चुना सूचकांक लिखें। कॉपी हुई लंबाई और साझा तत्व-भंडारण का अंतर रखें।
• प्रश्न 9, 10 और 11: हर कॉल का एक नोड बनाएँ, फिर केवल वर्तमान सक्रिय मूल-से-मौजूदा-कॉल रास्ते को चिन्हित करें। कुल नोड, अधिकतम सक्रिय कॉल और लौटा मान अलग संख्याएँ हैं।

प्रश्न 11 की छोटी हल की जाँच: mixed(3) पहले mixed(2) में जाता है; वह mixed(1) में जाता है, जो लौटता है, फिर mixed(0) में जाता है, जो लौटता है। mixed(2) से 2 लौटता है। उसके बाद ही मूल कॉल अपनी दूसरी अंदर वाली कॉल mixed(1) शुरू करती है। उससे 1 लौटता है, इसलिए मूल कॉल 3 लौटाती है। पाँचों कॉल कभी एक साथ सक्रिय नहीं थीं; अधिकतम तीन थीं। “पाँच” रटने के बजाय इस व्याख्या से गिनती की गलती पहचानें।

एक सटीक उपमा

helper में हर प्रवेश के लिए एक टिकट रखें। सारे टिकटों का ढेर कुल कॉल दर्ज करता है। अधूरे टिकटों का अलग स्टैक सक्रिय कॉल दर्ज करता है; अंदर वाली पूरी हो चुकी कॉल का टिकट, साथ की दूसरी शाखा शुरू होने से पहले उस स्टैक से हटता है। टिकट पर उत्तर के रूप में लिखी संख्या तीसरी चीज़ है। टिकट तार्किक ट्रेस में मदद करते हैं, C स्टैक के भौतिक भंडारण का दावा नहीं हैं।

अगली कोशिश के लिए मुख्य बातें

1. इनपुट की शर्त और लौटे परिणाम का अर्थ बताएँ।
2. अमान्य तत्व पढ़ने से पहले सीमा पर सुरक्षित लौटें।
3. हर caller की अपनी अवस्था और बाकी गणना रखें।
4. साझा ऐरे तत्व और कॉपी हुए पैरामीटर अलग पहचानें।
5. कुल कॉल और अधिकतम सक्रिय कॉल अलग गिनें।
6. उत्तर बदलने से पहले समझाएँ कि गलत विकल्प क्यों गलत है।

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

स्रोत टिप्पणी

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