रिकर्शन की कुल कॉल और सक्रिय फ़्रेम

दो गिनतियाँ दो अलग सवालों का उत्तर देती हैं

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

पूर्वापेक्षाएँ और पाठ का क्रम

पहले ये तीन पाठ पढ़ें:

1. रिकर्शन: आधार स्थिति और कॉल स्टैक: हर कॉल का अलग सामान्य पैरामीटर, प्रतीक्षा करता caller और आधार स्थिति वाली कॉल।
2. रिकर्शन का समापन और आधार स्थिति का चुनाव: स्वीकृत इनपुट-सीमा और यह तर्क कि हर रिकर्सिव चरण किसी return तक पहुँचता है।
3. रिकर्शन: लौटे मान और बची हुई गणना: अंदर वाली कॉल लौटने पर caller का ठीक वही रुका कथन आगे चलाना और लौटे मान को आर्ग्युमेंट से अलग रखना।

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

कोड और गिनती की शर्तें

हर उदाहरण C11 में है। इस पाठ के हर सहायक फ़ंक्शन के लिए शुरुआती int मान केवल 0 से 4 तक स्वीकार करें। अंदर की सभी कॉल के आर्ग्युमेंट भी इसी सीमा में रहते हैं। दिखाई गई सारी गणनाएँ और लौटे मान int की न्यूनतम अनिवार्य सीमा में भी समाते हैं। मानें कि इन छोटे निष्पादनों के लिए पर्याप्त संसाधन हैं। शिक्षार्थी के कोड में वैश्विक काउंटर, static स्थानीय चर, पॉइंटर से साझा लक्ष्य या समवर्ती कॉल नहीं हैं।

पूरे पाठ में यही गिनती नियम रखें:

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

यहाँ फ़्रेम स्रोत प्रोग्राम का ट्रेस बनाने वाला तार्किक रिकॉर्ड है। इन गिनतियों से मशीन के भौतिक फ़्रेम, स्टैक की बाइट-संख्या या सामान्य सुरक्षित रिकर्शन-सीमा तय नहीं होती। कंपाइलर आवश्यक व्यवहार बनाए रखते हुए कार्यान्वयन बदल सकता है।

पहले एक अंदर वाली कॉल की शृंखला गिनें

छपने वाले मान का अनुमान लगाएँ। फिर उससे अलग कुल कॉल और सक्रिय फ़्रेम की अधिकतम संख्या गिनें।

#include <stdio.h>

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

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

chain(3) में प्रवेश के आर्ग्युमेंट हैं 3 → 2 → 1 → 0। आधार वाली कॉल में प्रवेश के तुरंत बाद और उसके लौटने से पहले चारों कॉल अधूरी हैं। ऊपर की तीन कॉल प्रतीक्षा कर रही हैं। इसलिए कुल कॉल = 4 और अधिकतम सक्रिय फ़्रेम = 4 हैं।

घटनाओं की पूरी गिनती इस तरह है:

• आर्ग्युमेंट 3 पर प्रवेश: अब तक कुल 1, सक्रिय 1।
• आर्ग्युमेंट 2 पर प्रवेश: अब तक कुल 2, सक्रिय 2।
• आर्ग्युमेंट 1 पर प्रवेश: अब तक कुल 3, सक्रिय 3।
• आर्ग्युमेंट 0 पर प्रवेश: अब तक कुल 4, सक्रिय 4।
• आर्ग्युमेंट 0 से 1 लौटे: कुल 4 रहे, सक्रिय 3 हो जाएँ।
• आर्ग्युमेंट 1 से 3 लौटे: कुल 4 रहे, सक्रिय 2 हो जाएँ।
• आर्ग्युमेंट 2 से 5 लौटे: कुल 4 रहे, सक्रिय 1 रह जाए।
• आर्ग्युमेंट 3 से 7 लौटे: कुल 4 रहे, सक्रिय 0 हो जाएँ।

प्रोग्राम 7 छापता है। यह लौटा मान आधार के 1 में तीन बार 2 जोड़ने से आता है। यह दोनों कॉल-गिनतियों में से कोई नहीं है। शुरुआती इनपुट 0 पर फ़ंक्शन 1 लौटाता है; कुल कॉल 1 और अधिकतम सक्रिय संख्या 1 है।

इन सीधी शृंखलाओं में हर कॉल एक ही रास्ते पर है, इसलिए कुल कॉल और अधिकतम सक्रिय गिनती बराबर हैं। किसी दूसरे फ़ंक्शन पर यही बराबरी लगाने से पहले उसकी कॉल की बनावट देखनी होगी। शृंखला में भी कॉल की संख्या सटीक कदम और रुकने की शर्त पर निर्भर है; वह हमेशा शुरुआती इनपुट से एक अधिक नहीं होती।

अब हर गैर-आधार कॉल की दो अंदर वाली कॉल बनाएँ

इसे एक अलग प्रोग्राम के रूप में चलाएँ। अंदर वाली दोनों कॉल अलग-अलग घोषणा कथनों में लिखी हैं।

#include <stdio.h>

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

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

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

अंदर वाली दोनों कॉल split(n - 1) करती हैं और caller के अपने अपरिवर्तित n का इस्तेमाल करती हैं। बराबर आर्ग्युमेंट देने पर भी स्रोत-स्तर पर अलग कॉल होती हैं। प्रोग्राम पहले का परिणाम खोजकर दूसरी कॉल की जगह लगाने का कोई काम नहीं करता। दूसरी अंदर वाली कॉल चलते समय प्रतीक्षा करता caller अपना left रखता है, लेकिन पहली पूरी हो चुकी कॉल का फ़्रेम समाप्त हो चुका है।

स्वीकृत सीमा पर समापन का तर्क अब भी सरल है। हर अंदर वाली कॉल को छोटा गैर-ऋणात्मक पूर्णांक मिलता है; 0 तुरंत लौटता है। हर गैर-आधार कॉल केवल दो अंदर वाली कॉल करती है और उसका बचा हुआ काम सीमित है। इसलिए दोनों सीमित शाखाएँ पूरी हो सकती हैं। हम इन्हीं कॉल को गिन रहे हैं; इनपुट की शर्तें नहीं बढ़ा रहे।

split के इनपुट 2 का हल किया पेड़ और घटना क्रम

हर कॉल को अलग अक्षर दें, भले ही उसका आर्ग्युमेंट दोहराया जाए। ये अक्षर कॉल के नाम हैं, C प्रोग्राम के चर नहीं।

• A शुरुआती split(2) है।
• A की पहली अंदर वाली कॉल B है, यानी split(1)। B की पहली और दूसरी अंदर वाली कॉल C और D हैं; दोनों अलग-अलग split(0) हैं।
• B के पूरी तरह लौटने के बाद A की दूसरी अंदर वाली कॉल E है, यानी एक और split(1)। E की पहली और दूसरी अंदर वाली कॉल F और G हैं; दोनों अलग-अलग split(0) हैं।

पेड़ में सात नोड हैं: A, B, C, D, E, F और G। हर कॉल के लिए एक नोड गिनें। शुरुआती कॉल से आधार कॉल तक के सबसे लंबे रास्ते में तीन नोड हैं, जैसे A, B, C। इस पाठ में “रास्ते की लंबाई” का अर्थ दोनों सिरों सहित नोड की संख्या है; इस रास्ते में जोड़ने वाले किनारे केवल दो हैं।

अब प्रवेश और वापसी का वास्तविक क्रम देखें। नीचे हर सूची में सबसे पुराने से सबसे नए सक्रिय फ़्रेम लिखे हैं। खाली सूची का अर्थ है कि split की कोई कॉल सक्रिय नहीं बची।

1. A में प्रवेश: सक्रिय [A], अब तक कुल 1।
2. B में प्रवेश: सक्रिय [A, B], अब तक कुल 2।
3. C में प्रवेश: सक्रिय [A, B, C], अब तक कुल 3। यहाँ अधिकतम सक्रिय संख्या 3 पहुँचती है।
4. C से 1 लौटे: सक्रिय [A, B], कुल 3 रहे। B में अब left = 1 है।
5. D में प्रवेश: सक्रिय [A, B, D], अब तक कुल 4।
6. D से 1 लौटे: सक्रिय [A, B], कुल 4 रहे। B में अब right = 1 है।
7. B से 1 + 1 = 2 लौटे: सक्रिय [A], कुल 4 रहे। A में अब left = 2 है।
8. E में प्रवेश: सक्रिय [A, E], अब तक कुल 5। B, C और D समाप्त हो चुके हैं।
9. F में प्रवेश: सक्रिय [A, E, F], अब तक कुल 6।
10. F से 1 लौटे: सक्रिय [A, E], कुल 6 रहे। E में अब left = 1 है।
11. G में प्रवेश: सक्रिय [A, E, G], अब तक कुल 7।
12. G से 1 लौटे: सक्रिय [A, E], कुल 7 रहे। E में अब right = 1 है।
13. E से 2 लौटे: सक्रिय [A], कुल 7 रहे। A में अब right = 2 है।
14. A से 2 + 2 = 4 लौटे: सक्रिय [], कुल 7 रहे।

प्रोग्राम 4 छापता है, कुल 7 कॉल करता है और एक समय पर अधिकतम 3 तार्किक फ़्रेम सक्रिय होते हैं। प्रवेश का क्रम A, B, C, D, E, F, G है; लौटने का क्रम C, D, B, F, G, E, A है। कोई ऐसा क्षण नहीं आता जब B और E दोनों सक्रिय हों: एक ही caller की ये दो शाखाएँ एक के बाद एक चलती हैं।

कॉल का पेड़ पूरे निष्पादन की सभी कॉल रखता है। उस समय का तार्किक स्टैक केवल शुरुआती कॉल से वर्तमान कॉल तक की अधूरी कॉल रखता है। चित्र में दो शाखाएँ साथ रखने का अर्थ यह नहीं कि वे एक ही समय चल रही हैं।

कुल के लिए दोनों शाखाएँ जोड़ें और सक्रियता के लिए लंबा रास्ता लें

split की आधार कॉल के लिए दोनों गिनतियाँ 1 हैं। धनात्मक आर्ग्युमेंट पर:

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

split(2) की हर अंदर वाली शाखा में कुल 3 कॉल और अधिकतम 2 सक्रिय फ़्रेम हैं। इसलिए कुल = 1 + 3 + 3 = 7, जबकि अधिकतम सक्रिय = 1 + max(2, 2) = 3। यहाँ max बड़े मान के लिए गणितीय संकेत है; प्रोग्राम में इस्तेमाल किया गया C फ़ंक्शन नहीं।

स्वीकृत इनपुट के लिए यह छोटी जाँच-सूची पर्याप्त है:

• split(0): लौटा मान 1; कुल 1; अधिकतम सक्रिय 1।
• split(1): लौटा मान 2; कुल 3; अधिकतम सक्रिय 2।
• split(2): लौटा मान 4; कुल 7; अधिकतम सक्रिय 3।
• split(3): लौटा मान 8; कुल 15; अधिकतम सक्रिय 4।
• split(4): लौटा मान 16; कुल 31; अधिकतम सक्रिय 5।

दोहराए आर्ग्युमेंट एक नोड में नहीं मिल जाते: split(2) में 0 पर चार अलग आधार कॉल हैं। केवल अलग-अलग आर्ग्युमेंट 2, 1, 0 गिनने से 3 मिलेगा। यहाँ वह संयोग से अधिकतम सक्रिय गिनती है, कुल कॉल नहीं।

ये सटीक, सीमित गिनतियाँ आगे के विश्लेषण की तैयारी हैं। इस पाठ में पुनरावृत्ति संबंध हल करने की पूरी विधि, आसिम्प्टोटिक समय या स्थान जटिलता, मशीन के स्टैक की माप या शाखाओं वाले रिकर्शन का पूरा अध्ययन नहीं है।

एक सटीक उपमा

एक कर्मचारी काम की पर्चियाँ निपटा रहा है। अब तक खोली गई हर पर्ची का हिसाब एक रजिस्टर में रखें। दूसरी ओर केवल अधूरी पर्चियों का ढेर रखें। कोई पर्ची दो छोटे काम माँग सकती है, लेकिन कर्मचारी पहला काम पूरा करके उसकी पर्चियाँ हटाता है, फिर दूसरा काम खोलता है।

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

मुख्य बातें कॉल की गिनती

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

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

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

प्रश्न 1

पहले हल किए प्रोग्राम की chain परिभाषा लें। chain(0) के लिए (chain की कुल कॉल, एक ही समय सक्रिय chain फ़्रेम की अधिकतम संख्या) क्या है? शुरुआती और आधार स्थिति वाली कॉल गिनें; main और लाइब्रेरी कॉल छोड़ें।

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

प्रश्न 2

chain की परिभाषा बदले बिना chain(4) के लिए (लौटाया गया मान, chain की कुल कॉल, सक्रिय chain फ़्रेम की अधिकतम संख्या) कौन-सी तिकड़ी है? इस पाठ का गिनती नियम अपनाएँ।

A. (9, 4, 4) B. (5, 5, 5) C. (9, 5, 1) D. (9, 5, 5)

प्रश्न 3

दिखाई गई split परिभाषा के लिए split(3) में (split की कुल कॉल, सक्रिय split फ़्रेम की अधिकतम संख्या) क्या है? आधार स्थिति वाली सभी कॉल सहित हर कॉल गिनें।

A. (15, 4) B. (7, 3) C. (15, 15) D. (8, 4)

प्रश्न 4

हल किए split(2) ट्रेस में शुरुआती कॉल की पहली अंदर वाली कॉल पूरी लौट चुकी है और शुरुआती कॉल में left = 2 रखा जा चुका है। उसकी दूसरी अंदर वाली कॉल में अभी प्रवेश नहीं हुआ है। ठीक इस समय split के कितने फ़्रेम सक्रिय हैं? यहाँ इसी क्षण की गिनती पूछी गई है, पूरे निष्पादन की अधिकतम गिनती नहीं।

A. 3 B. 4 C. 1 D. 7

प्रश्न 5

इस अलग C11 प्रोग्राम में शुरुआती n के मान केवल 0 से 4 तक हैं। side_leaf(3) के दौरान (side_leaf की कुल कॉल, सक्रिय side_leaf फ़्रेम की अधिकतम संख्या) क्या है? हर गैर-आधार कॉल में अंदर वाली कॉल के दोनों कथन चलते हैं। main और लाइब्रेरी कॉल न गिनें।

#include <stdio.h>

int side_leaf(int n) {
    if (n == 0) {
        return 1;
    }
    int first = side_leaf(n - 1);
    int second = side_leaf(0);
    return first + second;
}

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

A. (7, 3) B. (15, 4) C. (4, 4) D. (7, 4)

प्रश्न 6

split(3) के स्रोत-स्तरीय ट्रेस में कुल 15 कॉल हैं और एक समय पर अधिकतम 4 तार्किक फ़्रेम सक्रिय हैं। केवल इन गिनतियों से कौन-सा निष्कर्ष सही निकलता है?

A. सबसे अधिक सक्रियता वाले क्षण पर कंपाइलर को ठीक चार भौतिक फ़्रेम रखने ही होंगे। B. ट्रेस कॉल और अधूरे कॉल-रिकॉर्ड गिनता है; मशीन के सटीक भंडारण और स्टैक की बाइट-संख्या के लिए अलग जानकारी चाहिए। C. फ़ंक्शन स्टैक में ठीक 4 * sizeof(int) बाइट लेता है। D. सभी पंद्रह कॉल एक ही समय चलती हैं।

उत्तर और हर विकल्प की वजह

उत्तर 1: B

A. गलत। शुरुआती कॉल फ़ंक्शन में प्रवेश करती है और आधार स्थिति जाँचती है। अंदर वाली कॉल न होने का अर्थ यह नहीं कि कोई कॉल हुई ही नहीं।

B. सही। ठीक एक कॉल होती है। वही शुरुआती कॉल भी है और आधार स्थिति वाली कॉल भी। लौटने तक वह सक्रिय रहती है।

C. गलत। शर्त जाँचते और 1 लौटाते समय यह एक कॉल सक्रिय है, इसलिए सक्रिय फ़्रेम की अधिकतम संख्या भी 1 है।

D. गलत। यहाँ शुरुआती कॉल और आधार स्थिति वाली कॉल एक ही कॉल के दो विवरण हैं। उसे दो बार न गिनें।

उत्तर 2: D

A. गलत। लौटा मान 9 सही है, लेकिन 4, 3, 2, 1 और 0 आर्ग्युमेंट से पाँच कॉल होती हैं। इस विकल्प में किसी एक छोर की कॉल छूट गई है।

B. गलत। दोनों कॉल-गिनतियाँ सही हैं। आधार स्थिति 1 लौटाती है और चारों प्रतीक्षा कर रहे caller 2 जोड़ते हैं। इससे 5 नहीं, 9 मिलता है।

C. गलत। प्रतीक्षा कर रहे ऊपर के caller भी सक्रिय रहते हैं। आधार स्थिति पर chain की पाँचों कॉल अधूरी हैं, भले ही उस क्षण केवल आधार वाली कॉल चल रही हो।

D. सही। 0 से 4 तक आर्ग्युमेंट के लौटे मान 1, 3, 5, 7 और 9 हैं। एकमात्र रास्ते में पाँच नोड हैं, इसलिए कुल कॉल और अधिकतम सक्रिय फ़्रेम, दोनों 5 हैं।

उत्तर 3: A

A. सही। पेड़ के स्तरों में 1, 2, 4 और 8 कॉल हैं, जिनका कुल 15 है। सबसे लंबे सक्रिय रास्ते में आर्ग्युमेंट 3, 2, 1, 0 हैं, इसलिए 4 फ़्रेम हैं।

B. गलत। ये split(2) की गिनतियाँ हैं। split(3) के पेड़ का अतिरिक्त स्तर आठ नोड जोड़ता है, जिससे कुल 7 से 15 होता है; सबसे लंबा रास्ता तीन से चार नोड का हो जाता है।

C. गलत। कुल कॉल 15 हैं, लेकिन पूरी हो चुकी दूसरी शाखाएँ सक्रिय नहीं रहतीं। एक समय पर केवल शुरुआती कॉल से वर्तमान कॉल तक का रास्ता सक्रिय है।

D. गलत। आठ केवल आधार स्थिति वाली पत्तियों की गिनती है; यहाँ उनके योग के बराबर मान लौटता भी है। सात गैर-आधार कॉल भी गिननी होंगी।

उत्तर 4: C

A. गलत। आधार वाली कॉल चलते समय अधिकतम तीन फ़्रेम सक्रिय होते हैं। बताए गए क्षण तक पहली अंदर वाली कॉल की पूरी शाखा लौट चुकी है।

B. गलत। अब तक चार कॉल में प्रवेश हुआ है: शुरुआती कॉल और उसकी पहली शाखा की तीन कॉल। उनमें से तीन पूरी हो चुकी हैं।

C. सही। केवल शुरुआती कॉल अधूरी है। उसके स्थानीय left में लौटा हुआ पूर्णांक रखा है; उस मान को रखने से पूरी हो चुकी अंदर वाली कॉल का फ़्रेम सक्रिय नहीं रहता।

D. गलत। सात पूरे निष्पादन की कुल कॉल हैं। दूसरी शाखा अभी शुरू नहीं हुई है और समाप्त कॉल सक्रिय नहीं हैं।

उत्तर 5: D

A. गलत। कुल सात सही है। सबसे लंबा रास्ता 3, 2, 1, 0 है, जिसमें चार नोड हैं; तीन तो उन्हें जोड़ने वाले किनारों की गिनती है।

B. गलत। दूसरी अंदर वाली कॉल को हमेशा 0 मिलता है और वह तुरंत लौटती है। split की तरह उससे n - 1 की एक और पूरी शाखा नहीं बनती।

C. गलत। चार अधिकतम सक्रिय फ़्रेम की संख्या है और यहाँ लौटा मान भी है। कुल कॉल के लिए पहली अंदर वाली कॉलों के चार-नोड रास्ते में n = 1, 2 और 3 पर होने वाली तीन अलग दूसरी कॉल जोड़ें।

D. सही। पहली अंदर वाली कॉलों के रास्ते में आर्ग्युमेंट 3, 2, 1, 0 आते हैं; तीनों धनात्मक कॉल 0 पर एक अलग आधार कॉल भी करती हैं। कुल 4 + 3 = 7 है और सबसे लंबे सक्रिय रास्ते में 4 फ़्रेम हैं।

उत्तर 6: B

A. गलत। तार्किक फ़्रेम स्रोत-स्तर पर निष्पादन समझाने का मॉडल हैं। आवश्यक व्यवहार बनाए रखते हुए कार्यान्वयन कोड बदल सकता है; गिनती भौतिक रिकॉर्ड की बनावट तय नहीं करती।

B. सही। दोनों गिनतियाँ इस ट्रेस के तार्किक सवालों का उत्तर देती हैं। उनसे कंपाइलर का अनुकूलन, फ़्रेम की बनावट, स्टैक की सटीक बाइट-संख्या या सामान्य सुरक्षित इनपुट-सीमा तय नहीं होती।

C. गलत। sizeof(int) एक int ऑब्जेक्ट का आकार बताता है, पूरे कॉल फ़्रेम का नहीं। केवल तार्किक गिनती से भंडारण का ऐसा सटीक सूत्र नहीं मिलता।

D. गलत। अंदर वाली कॉल क्रम से होती हैं। प्रतीक्षा कर रहे caller सक्रिय हैं, पर अपना अगला कथन नहीं चला रहे। पूरे निष्पादन का कुल, एक साथ चल रही कॉल की संख्या नहीं है।