Comprendre la récursivité avec la série Fibonacci

Question

J'essaie de mieux comprendre la récurrence et le fonctionnement des instructions de retour. En tant que tel, je regarde un morceau de code destiné à identifier le nombre de fibonacci associé à un terme donné - dans ce cas, 4. J'ai du mal à comprendre l'autre déclaration.

def f(n): 
    if n == 0: 
    return 0 
    if n == 1: 
    return 1 
    else: 
    return f(n-1) + f(n-2) 

f(4) 

J'ai essayé d'utiliser Python pour examiner Visualize ce qui se passe à chaque étape, mais je me perdre quand il frappe l'instruction else.

On dirait qu'il prend la valeur de n et soustrait 1, pour créer une n nouvelle valeur de 3 qu'il retourne à la définition de la fonction. Il semble donc renvoyer uniquement la valeur de la première fonction dans l'instruction else. Cependant, l'instruction else est écrite pour renvoyer la somme de 2 fonctions f (n-1) + f (n-2), auquel cas je pensais que la valeur de retour serait 5? Pouvez-vous même ajouter 2 fonctions ensemble?

Merci d'avance pour votre aide.

Voici un lien vers le code Python Visualize Sum of 2 functions

Answer 1

En cas de doute, juste le décomposer.

Le flux d'arbre est en fait contre-intuitif de flux de contrôle réel, mais une fois que vous comprenez la séquence d'appels, il devient plus clair. La chose à comprendre ici est que vous continuez à décomposer un calcul plus grand en une somme de calculs plus petits, et vous vous arrêtez lorsque vous frappez le cas de base (les instructions if). Maintenant, vous pouvez effectuer tous les petits calculs, et combiner les résultats de ces petits calculs pour former un résultat plus grand et plus grand, jusqu'à ce que vous ayez votre réponse finale.

Chaque fois qu'un appel récursif atteint le cas de base, il renvoie 1 ou 0, selon le cas qui a été touché. Cette valeur sera renvoyée à l'appelant précédent. Pour comprendre, pensez à:

f(1)3 + f(0)3

Notez ici que l'indice représente la profondeur de l'arbre d'appel de récursivité. L'appel est fait par f(2)2. f(1)3 est calculé en premier et 1 est renvoyé à f(2)2. f(0)3 est ensuite calculé et 0 est renvoyé à f(2)2. Les deux valeurs de retour sont additionnées et le résultat est 1.

f(2)2 puis retours1 à celui appelé il, qui dans ce cas se trouve être f(3)1. f(3)1 appelé f(2)2 + f(1)2, pendant ce que l'autre f(1)2 renvoie également 1 à f(3)1, qui ajoute maintenant cela avec le résultat de f(2)2, pour former 2.

f(3)1 passe maintenant 2-f(4)0, son appelant, ce qui est arrivé à appeler f(3)1 + f(2)1 ... et il va.

---

Une autre façon de regarder est de commencer dès le premier appel de la fonction qui est en fait: f(4)0.

f(4)0 calcule f(3)1 + f(2)1. Mais pour calculer f(3)1, il doit savoir f(2)2 + f(1)2, et de même, pour calculer f(2)1, il doit savoir f(1)2 + f(0)2, et ainsi de suite.

Answer 2

Ajout des instructions d'impression peut également aider à clarifier la séquence:

def f(n): 
    print("Number received:", n) 
    if n == 0: 
     return 0 
    if n == 1: 
     return 1 
    else: 
     print("---- First recursion ----") 
     a = f(n-1) 
     print("---- Second recursion ----") 
     b = f(n-2) 
     print(" a=:",a,"; b=",b,"; returning:", a+b) 
     return a + b 

print("Final f(4)=", f(4)) 

Sortie:

Number received: 4 
---- First recursion ---- 
Number received: 3 
---- First recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
---- Second recursion ---- 
Number received: 1 
a=: 1 ; b= 1 ; returning: 2 
---- Second recursion ---- 
Number received: 2 
---- First recursion ---- 
Number received: 1 
---- Second recursion ---- 
Number received: 0 
a=: 1 ; b= 0 ; returning: 1 
a=: 2 ; b= 1 ; returning: 3 
Final f(4)= 3