C++
C ++ में पुनरावृत्ति

Fibonnaci अनुक्रम को हल करने के लिए पूंछ की पुनरावृत्ति और Fibonnaci शैली की पुनरावृत्ति का उपयोग करना

फिबोनासी अनुक्रम के Nth शब्द को प्राप्त करने के लिए पुनरावर्तन का उपयोग करने का सरल और सबसे स्पष्ट तरीका यह है

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

हालांकि, यह एल्गोरिथ्म उच्च पदों के लिए पैमाने पर नहीं है: बड़े और बड़े n , फ़ंक्शन कॉल की संख्या जो आपको तेजी से बढ़ने की आवश्यकता है। यह एक साधारण पूंछ पुनरावृत्ति के साथ बदला जा सकता है।

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

फ़ंक्शन के लिए प्रत्येक कॉल अब तुरंत फ़ाइबोनेसी अनुक्रम में अगले शब्द की गणना करता है, इसलिए फ़ंक्शन कॉल की संख्या n रैखिक रूप से आती है।

संस्मरण के साथ पुनरावृत्ति

पुनरावर्ती कार्य काफी महंगा हो सकता है। यदि वे शुद्ध कार्य हैं (कार्य जो समान तर्कों के साथ बुलाए जाने पर हमेशा समान मान लौटाते हैं, और जो न तो बाहरी स्थिति को संशोधित करते हैं और न ही निर्भर करते हैं), तो उन्हें पहले से गणना किए गए मूल्यों को संग्रहीत करके स्मृति की कीमत पर काफी तेज बनाया जा सकता है।

निम्नलिखित संस्मरण के साथ फिबोनाची अनुक्रम का कार्यान्वयन है:

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

ध्यान दें कि सरल पुनरावर्तन सूत्र का उपयोग करने के बावजूद, पहले कॉल पर यह फ़ंक्शन $ O (n) $ है। समान मूल्य वाली बाद की कॉल पर, यह निश्चित रूप से $ O (1) $ है।

हालांकि यह ध्यान दें कि यह कार्यान्वयन रीएन्ट्रेंट नहीं है। इसके अलावा, यह संग्रहीत मूल्यों से छुटकारा पाने की अनुमति नहीं देता है। एक वैकल्पिक कार्यान्वयन अतिरिक्त तर्क के रूप में मानचित्र को पारित करने की अनुमति देना होगा:

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

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