Salut,

En essayant de répondre à un post, je me suis replongé dans la récurrence (mal de crâne assuré à chaque fois ). Bref, j'essaie de refaire la suite de Fibonacci et j'en arrive au code suivant (sûrement pas le meilleur ):

def fibo(n, lst=None):
    if not lst:
        lst = [0, 1]
    if n:
        lst.append(sum(lst[-2:]))
        fibo(n-1, lst)
    else:
        print(lst)  #La liste vaut bien quelque chose
        return lst  #Mais il me renvoie None

print(fibo(10))

Si vous lancez ce petit programme, vous verrez que la ligne 8 m'affiche bien la valeur de lst. Or à la ligne suivante, au lieu de me renvoyer cette valeur il me renvoie None. Quelqu'un pourrait-il m'expliquer le pourquoi de ce résultat svp ?

PS: J'ai pensé que c'était dû au None en argument, mais apparemment ce n'est pas le cas car j'ai essayé d'entrer une autre valeur (une liste vide en l'occurrence []) et il me renvoie toujours None.

PS2: Le seul moment où il me renvoie un résultat c'est quand je prends n=0). Donc le problème vient bien de la récurrence. Mais pourquoi?

-
Edité par Olygrim 6 février 2016 à 19:20:25

Salut,

Il me semble que c'est parce que la valeur renvoyée est retournée au dernier appel de ta fonction, en clair, renvoyée en plein milieu de ta boucle if lors de l'avant dernier appel de la fonction, qui n'a pas moyen de capter cette valeur, et qui au final, ne renvoie donc rien.

Je n'arrive pas à expliquer correctement, c'est compliqué... Mais je pense que le fait que la liste ne soit pas retournée au premier appel de ta fonction, mais au précèdent, devrait te permettre de comprendre. 

EDIT : Oui voilà c'était bien ça, regarde ce bout de code :

def fibo(n, lst=None):
    if not lst:
        lst = [0, 1]
    if n:
        lst.append(sum(lst[-2:]))
        return fibo(n-1, lst)
    else:
        print(lst)  #La liste vaut bien quelque chose
        return lst  #Mais il me renvoie None
 
print(fibo(10))

Il fonctionne parfaitement.

-
Edité par Grimmys 6 février 2016 à 20:28:11

Ton algo remplie la liste en montant, mais il ne fait pas suivre le résultat en redescendant. (return fibo(n-1, lst))

C'est à cause de la récurrence justement...

Si tu exécutes ton code "à la main" pour une valeur d'entrée égale à 1 on a:

• not lst est vrai donc lst devient [0,1] (normalement c'est [1,1] dans la suite classique non?)
• n est bien différent de 0 donc on ajoute 2 et on part en récursion avec fibo(0):
  
  • n est égal à 0 donc on affiche la liste et on la retourne

  Le résultat retourné par fibo(0) ne sert à rien, on sort de la fonction avec la valeur None comme il n'y a pas de return.

Donc pour régler le problème il suffit de rajouter un return devant ton appel récursif de fibo, pour propager la valeur de retour à toutes les fonctions fonctions appelantes jusqu'à atteindre l'appel principal et retourner la valeur obtenue. En gros:

def fibo(n, lst=None):
    if not lst:
        lst = [0, 1]
    if n:
        lst.append(sum(lst[-2:]))
        return fibo(n-1, lst)
    else:
        print(lst)  #La liste vaut bien quelque chose
        return lst  #Mais il me renvoie None
 
print(fibo(10))

Sortie:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

EDIT: Doublé!

-
Edité par Anonyme 6 février 2016 à 20:28:03

Super. Merci à tous j'ai enfin compris . Dans une récurrence, La valeur de retour est celle du premier appel. Et effectivement, au premier appel je ne renvoie rien (ou en d'autre mot, je ne récupère rien), car n>0 et n'ayant pas mis de return dans mon if, ça me renvoie None.

Il faut quand même que je travaille cette propagation pour bien la maîtriser car c'est pas encore super limpide dans ma tête .

En tous cas, merci à vous pour cet éclaircissement 

-
Edité par Olygrim 6 février 2016 à 21:03:43