क्या सी

Question

में रिकर्सन गहराई पर कोई हार्ड-वायर्ड सीमा है, चर्चा के तहत कार्यक्रम recursion का उपयोग करके sum-of-first-n-natural-numbers की गणना करने का प्रयास करता है। मुझे पता है कि यह एक साधारण सूत्र n*(n+1)/2 का उपयोग करके किया जा सकता है लेकिन यहां विचार recursion का उपयोग करना है।

#include <stdio.h> 

unsigned long int add(unsigned long int n) 
{ 
    return (n == 0) ? 0 : n + add(n-1); 
} 

int main() 
{ 
    printf("result : %lu \n", add(1000000)); 
    return 0; 
} 

कार्यक्रम n = 100,000 के लिए अच्छी तरह से काम, लेकिन जब n का मूल्य 1,000,000 लिए बढ़ा दिया गया था कि यह एक Segmentation fault (core dumped)

के परिणामस्वरूप निम्नलिखित gdb संदेश से लिया गया है:

कार्यक्रम इस प्रकार है ।

Program received signal SIGSEGV, Segmentation fault. 
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8 
) at k.c:4 

मेरा प्रश्न (ओं):

1. वहाँ C में recursion depth पर किसी भी कड़ी मेहनत से तार सीमा है? या recursion depth उपलब्ध स्टैक मेमोरी पर निर्भर करता है?

2. किसी प्रोग्राम को रीसाइजजीवी सिग्नल क्यों प्राप्त होगा, इसके संभावित कारण क्या हैं?

Answer 1

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

• कुछ कार्यान्वयन के लिए एक तकनीक है, जहां वे रन टाइम पर नए स्टैक क्षेत्रों आवंटित कर सकते हैं हो सकता है। लेकिन सामान्य रूप से, वे नहीं करते हैं।

• कुछ फ़ंक्शन थोड़ा अधिक अप्रत्याशित तरीकों से ढेर का उपभोग करेंगे, जैसे कि जब वे एक चर-लंबाई सरणी आवंटित करते हैं।

• कुछ फ़ंक्शंस को पूंछ-कॉल का उपयोग करने के लिए संकलित किया जा सकता है जो स्टैक स्पेस को सुरक्षित रखेगा। कभी-कभी आप अपने फ़ंक्शन को फिर से लिख सकते हैं ताकि सभी कॉल (जैसे स्वयं के लिए) आखिरी चीज के रूप में होती हैं, और आपके कंपाइलर को इसे अनुकूलित करने की अपेक्षा करते हैं।

ऐसा नहीं है कि देखने के लिए वास्तव में बहुत ढेर कैसे अंतरिक्ष एक समारोह के प्रत्येक कॉल के लिए आवश्यक है आसान नहीं है, और यह संकलक के अनुकूलन के स्तर के अधीन किया जाएगा।आपके मामले में ऐसा करने का एक सस्ता तरीका &n प्रत्येक बार कॉल करने के लिए प्रिंट करना होगा; n स्टैक पर होगा (विशेष रूप से जब से प्रोग्राम को अपना पता लेना होगा - अन्यथा यह एक रजिस्टर में हो सकता है), और इसके लगातार स्थानों के बीच की दूरी ढेर फ्रेम के आकार को इंगित करेगी।

Answer 2

सी में प्रत्यावर्तन गहराई तक कोई सैद्धांतिक सीमा केवल सीमा आम तौर पर सीमित ढेर अंतरिक्ष अपने कार्यान्वयन के उन लोगों के, कर रहे हैं नहीं है।
(ध्यान दें कि सी मानक वास्तव में एक ढेर आधारित कार्यान्वयन की आवश्यकता नहीं है। मैं किसी भी वास्तविक दुनिया कार्यान्वयन कि आधारित ढेर नहीं कर रहे हैं के बारे में पता नहीं है, लेकिन रखें कि मन में।)

एक SIGSEGV किसी भी चीज के कारण हो सकता है, लेकिन आपकी स्टैक सीमा से अधिक अपेक्षाकृत आम है। एक खराब सूचक को अस्वीकार करना एक और है।

Answer 3

सी मानक फ़ंक्शन कॉल के लिए न्यूनतम समर्थित गहराई को परिभाषित नहीं करता है। अगर ऐसा होता है, तो वैसे भी गारंटी देने में काफी मुश्किल होती है, तो यह धारा 5.2.4 Environmental limits में कहीं भी उल्लेख किया होगा।

Answer 4

1) ढेर की खपत को कम करने और पूंछ रिकर्सन ऑप्टिमाइज़ेशन के रूप में लिखा जाने की उम्मीद है।

जीसीसी -O3 prog.c

#include <stdio.h> 

unsigned long long int add(unsigned long int n, unsigned long long int sum){ 
    return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form 
} 

int main(){ 
    printf("result : %llu \n", add(1000000, 0));//OK 
    return 0; 
} 

दो प्रश्नों के लिए