Rekursion in der Tiefe (Python)

Question

Überprüfen Sie den folgenden Code ein:

>>> def fib(x): 
... if x == 0 or x == 1: 
...  return 1 
... else: 
...  return fib(x-1) + fib(x-2) 
>>> print(fib(4)) 

Nach den Ausführungen im SoloLearn Python Tutorial (für Rekursion), funktioniert der Code wie folgt aus:

1. fib(4) = fib(3) + fib(2) 
2. = (fib(2) + fib(1)) + (fib(1) + fib(0)) 
3. = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) 
4. = 1+ 1 + 1 + 1 + 1 
5. = 5 

Nach Linie 2, nur fib(2) sollte der sonst Teil der fib() Funktion gehen, richtig? Die beiden fib(1) und die einzelnen fib(0) erfüllen die Kriterien der if Teil der fib() Funktion. Also wird 1 zurückgegeben. Meine Frage ist, warum in der 3. Zeile fib(1) + fib(0) + fib(1) + fib(1) + fib(0) alle durch 1 ersetzt und dann hinzugefügt werden?

Verzeih mir, dass ich eine solche Frage gestellt habe.

Answer 1

@MorganThrapp ist korrekt. Mehr das Basismodell der rekursiven Funktion speziell, fib ist:

if x==0 or x==1: 
    return 1 

Diese Klausel wird ausgelöst, wenn fib(1) oder fib(0) genannt wird. Im Programmiersprachgebrauch wertet die Funktion auf ihren Rückgabewert aus, der hier 1 ist.

In Ihrem Beispiel von fib(4), wird fib fünfmal genannt entweder mit einem 1 oder einem 0 Eingang und diese Ergebnisse sind alle zusammen addieren, und dass die Ergebnisse in der endgültigen Rückgabewert von 5, die von dem ursprünglichen Anruf fib(4) zurückgegeben und ging sofort in die print Funktion über.

Answer 2

Ich glaube die Beschreibung, wie der Code funktioniert, ist irreführend, da es zu zeigen scheint, dass nicht alle Werte ausgewertet werden, wenn man von einer Zeile zur nächsten geht. Wenn wir in der nächsten Zeile alles durch die aufgerufenen Funktionen ersetzen (oder den Wert, den es zurückgibt) und Klammern setzen wie in Ihrem Beispiel, erhalten wir Folgendes, das Ihnen helfen könnte, die inneren Abläufe dieses Codes besser zu verstehen:

1. fib(4) 
2. = fib(3) + fib(2) 
3. = (fib(2) + fib(1)) + (fib(1) + fib(0)) 
4. = ((fib(1) + fib(0)) + 1) + (1 + 1) 
5. = 1 + 1 + 1 + 2 
6. = 5 

Answer 3

dies ist eine doppelte rekursive Funktion, so seine Forderung eine Baumstruktur von Anrufen mit dem Basisfall von fib (1) und fib führt (0)

fib(4) =     fib(3)   +  fib(2)  
         / \    / \ 
fib(4) =  ( fib(2) + fib(1)) + (fib(1) + fib(0))  
       / \   |    |  | 
fib(4) = ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))  
       |  |   |   |  | 
fib(4) = (( 1 + 1 ) + 1 ) + ( 1 + 1 )  
        \ /   |    \ /
fib(4) = ((  2  ) + 1 ) + (  2  )  
         \  /     | 
fib(4) = (     3   ) + (  2  )  
            \   /
fib(4) =         5 

Sie die Arbeit der Funktion auch visualisieren durch Hinzufügen einiger Abzüge an den richtigen Stellen und ein zusätzliches Hilfsargument, um damit zu helfen und einige andere geringfügige Änderungen

>>> def fib(n, nivel=0): 
     if n==0 or n==1: 
      print(" "*nivel,"fib(",n,")=1") 
      return 1 
     else: 
      print(" "*nivel,"fib(",n,")") 
      result = fib(n-1,nivel+1) + fib(n-2,nivel+1) 
      print(" "*nivel,"fib(",n,")=",result) 
      return result 

>>> fib(4) 
fib(4) 
    fib(3) 
    fib(2) 
    fib(1)=1 
    fib(0)=1 
    fib(2)= 2 
    fib(1)=1 
    fib(3)= 3 
    fib(2) 
    fib(1)=1 
    fib(0)=1 
    fib(2)= 2 
fib(4)= 5 
5 
>>> 

hier können Sie feststellen, dass der Anruf in der Folge nach rechts und unten von links nach oben aufgelöst werden