फाइबोनैचि समारोह प्रश्न

Question

मैं फाइबोनैचि अनुक्रम की गणना की गई और इस कोड भर में ठोकर खाई है, जो मैं एक बहुत देखा:

int Fibonacci (int x) 
{ 
    if (x<=1) { 
     return 1; 
    } 
    return Fibonacci (x-1)+Fibonacci (x-2); 
} 

मैं क्या समझ में नहीं आता कि यह कैसे अंत में काम करता है, विशेष रूप से वापसी हिस्सा है : क्या यह फिर से फिबोनाची फ़ंक्शन को कॉल करता है? क्या कोई मुझे इस समारोह के माध्यम से कदम उठा सकता है?

Answer 1

हां, फ़ंक्शन स्वयं कॉल करता है। उदाहरण के लिए,

Fibonacci(4) 
= Fibonacci(3) + Fibonacci(2) 
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0)) 
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1) 
= ((1 + 1) + 1) + 2 
= (2 + 1) + 2 
= 3 + 2 
= 5 

ध्यान दें कि फाइबोनैकी फ़ंक्शन को 9 बार यहां कहा जाता है। आम तौर पर, भद्दा रिकर्सिव फाइबोनैकी फ़ंक्शन में exponential running time होता है, जो आमतौर पर एक खराब बात है।

Answer 2

यह recursive function का एक शास्त्रीय उदाहरण है, जो एक कार्य है जो स्वयं को कॉल करता है।

आप इसे ध्यान से पढ़ें, तो आप,,, देखेंगे कि यह अपने आप में फोन करेगा, या recurse, बार बार जब तक यह तथाकथित आधार मामले पर पहुंच जाने पर x <= 1 जो उस समय शुरू कर देंगे "बैक ट्रैक" और गणना मानों को जोड़ना।

invoked with 3 
Recursing on 2 and 1 
    invoked with 2 
    Recursing on 1 and 0 
     invoked with 1 
     x = 1, base case reached. 
     invoked with 0 
     x = 0, base case reached. 
    returning 2 
    invoked with 1 
    x = 1, base case reached. 
returning 3 

Fibonacci of 3: 3 

का पता लगाने के एक पेड़ चित्रण लगेगा

की तरह कुछ

       fib 4 
       fib 3    +   fib 2 
    fib 2  + fib 1    fib 1 + fib 0 
fib 1 + fib 0   1     1  1 
    1  1 

:

public class Test { 

    static String indent = ""; 

    public static int fibonacci(int x) { 

     indent += " "; 
     System.out.println(indent + "invoked with " + x); 

     if (x <= 1) { 

      System.out.println(indent + "x = " + x + ", base case reached."); 
      indent = indent.substring(4); 

      return 1; 
     } 

     System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2)); 
     int retVal = fibonacci(x-1) + fibonacci(x-2); 
     System.out.println(indent + "returning " + retVal); 
     indent = indent.substring(4); 
     return retVal; 

    } 


    public static void main(String... args) { 
     System.out.println("Fibonacci of 3: " + fibonacci(3)); 
    } 
} 

उत्पादन निम्नलिखित है:

निम्नलिखित कोड स्पष्ट रूप से कलन विधि का पता लगाने के लिए बाहर प्रिंट

पुनरावर्ती कार्यों को लिखते समय सोचने के महत्वपूर्ण भाग हैं:

1. आधार मामले की लें देखभाल

अगर हम ऊपर के उदाहरण में if (x<=1) return 1; भूल गया था क्या हुआ होता?

2. सुनिश्चित पुनरावर्ती कॉल किसी भी तरह आधार मामले

अगर हम गलती से एल्गोरिथ्म संशोधित fibonacci(x)+fibonacci(x-1);

Answer 3

इस क्लासिक समारोह प्रत्यावर्तन है वापस जाने के लिए क्या हुआ है | की ओर कम हो बनाओ। http://en.wikipedia.org/wiki/Recursive_function आपको शुरू करना चाहिए। अनिवार्य रूप से यदि एक्स 1 से कम या उसके बराबर है तो यह 1 लौटाता है। अन्यथा यह प्रत्येक चरण में एक्स चलने वाले फाइबोनैकी को कम करता है।

Answer 4

हां, फाइबोनैकी फ़ंक्शन को फिर से बुलाया जाता है, इसे रिकर्सन कहा जाता है।

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

ध्यान दें कि रिकर्सन कठिन है क्योंकि आप एक ही फ़ंक्शन को असीमित रूप से फिर से कॉल कर सकते हैं और कॉल स्टैक भर सकते हैं। इन त्रुटियों को "स्टैक ओवरफ़्लो" कहा जाता है (यहां यह है!)

Answer 5

सी और अन्य भाषाओं में, किसी फ़ंक्शन को किसी अन्य फ़ंक्शन की तरह ही कॉल करने की अनुमति है। इसे रिकर्सन कहा जाता है।

यदि यह अजीब लगता है क्योंकि यह आपके द्वारा लिखे गए लूप से अलग है, तो आप सही हैं। यह रिकर्सन का बहुत अच्छा अनुप्रयोग नहीं है, क्योंकि n वें फाइबोनैकी संख्या को n -1th ढूंढने के लिए दो बार आवश्यकता होती है, जिससे n में चलने का समय घातीय हो जाता है।

पुनरावृत्ति फाइबोनैचि अनुक्रम में, अगले पर जाने से पहले पिछले फिबोनैकी संख्या याद क्रम में n रैखिक, जिस तरह से यह होना चाहिए बेहतर बनाता है।

रिकर्सन स्वयं भयानक नहीं है। वास्तव में, पाश मैं सिर्फ वर्णित (और किसी भी लूप) एक पुनरावर्ती समारोह के रूप में लागू किया जा सकता:

int Fibonacci (int x, int a = 1, int p = 0) { 
    if (x == 0) return a; 
    return Fibonacci(x-1, a+p, a); 
} // recursive, but with ideal computational properties 

Answer 6

वापसी फाइबोनैचि (एक्स 1) + फाइबोनैचि (एक्स 2);

यह बहुत अक्षम है।

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c) 
{ 
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c); 
} 

unsigned fibonacci(unsigned n) 
{ 
    return (n < 2) ? n : fibonacci(n, 0, 1, 1); 
} 

फाइबोनैचि अनुक्रम कार्यात्मक भाषाओं में और अधिक संक्षेप में व्यक्त किया जा सकता है: मैं निम्नलिखित रैखिक वैकल्पिक सुझाव देते हैं।

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci) 

> take 12 fibonacci 
[0,1,1,2,3,5,8,13,21,34,55,89] 

Answer 7

के रूप में अपने प्रश्न सी ++ चिह्नित है, मैं बाहर बिंदु है कि यह समारोह भी एक टेम्पलेट के रूप संकलन समय पर प्राप्त किया जा सकता मजबूर महसूस, आप के साथ इसका इस्तेमाल करने के एक संकलन समय चर होना चाहिए।

template<int N> struct Fibonacci { 
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value; 
}; 
template<> struct Fibonacci<1> { 
    const static int value = 1; 
} 
template<> struct Fibonacci<0> { 
    const static int value = 1; 
} 

कुछ समय बाद मैंने लिखा था, इसलिए यह थोड़ा सा हो सकता है, लेकिन यह होना चाहिए।

Answer 8

या यदि आप अधिक तेज़ी से बनना चाहते हैं लेकिन अधिक मेमोरी का उपयोग करें इसका उपयोग करें।

int *fib,n; 
void fibonaci(int n) //find firs n number fibonaci 
{ 
fib= new int[n+1]; 
fib[1] = fib[2] = 1; 
for(int i = 3;i<=n-2;i++) 
    fib[i] = fib[i-1] + fib[i-2]; 
} 

और एन = 10 उदाहरण के लिए के लिए आप होगा: मिथ्या [1] मिथ्या [2] मिथ्या [3] मिथ्या [4] मिथ्या [5] मिथ्या [6] मिथ्या [7] मिथ्या [8 ] फाइब [9] फाइब [10] 1 1 2 3 5 8 13 21 34 55``