Discussion :

[marven]

Bonjour à tous,

je lis actuellement le livre "Plonger au cœur de python" >LIEN< et cet exemple m'interroge (expl 2.6).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def fib(n):
    print ('n =', n)
    if n > 1:
        return n * fib(n - 1)
    else:
        print ('end of the line')
        return 1
###    
if __name__ == "__main__":
fib(5)
 
 
"""   voici le resultat
>>> 
n = 5
n = 4
n = 3
n = 2
n = 1
end of the line
>>> 
"""

Je ne comprends pas le fonctionnement du n * dans return n * fib(n - 1)
return fib(n - 1) fonctionne de la même manière. (C'est à dire que return déclenche à nouveau l'utilisation de fib(). )
comment fonctionne return n * fib(n - 1) ?

Pouvez-vous m’éclairer ?

[wiztricks]

Salut,

comment fonctionne return n * fib(n - 1)

çà retourne juste le produit de "n" avec le retour de la fonction fib appelée avec n-1.
La multiplication vous connaissez?

- W

[marven]

Je connais la multiplication, merci.
Mais pourquoi n*fip(n - 1) retourne la même chose que fip(n - 1) ? Sans multiplication.

(Cet exemple n'a peu-être pas d'application réelle, c'est juste pour montrer un mécanisme de fonction pour le livre ?)

[VinsS]

Salut,

Tout d'abord pourquoi fib() ? Dans les cours il s'agit généralement d'une fonction retournant la suite de Fibonnaci.

Ton exemple est une fonction récursive (qui s'appelle elle-même) et si tu avais ajouté un dernier print tu aurais vu ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
>>> def fact(n):
...     print('n = ', n)
...     if n > 1:
...             return n * fact(n - 1)
...     else:
...             return n
... 
>>> print(fact(5))
n =  5
n =  4
n =  3
n =  2
n =  1
120

C'est donc la factorielle de 5

[marven]

Merci beaucoup pour ta super réponse VinsS.

Je crois mieux comprendre : que n dans fact(5) prend la valeur de n-1 à chaque boucle (tant que n>1). Tandis que fact(5), lui-même étant un type (int), prends la valeur du produit de n * fact(n-1) à chaque boucle jusqu'à n>1 aussi.
Donc une factorielle.

C'est un peu comme une variable qui se calculerait elle-même.

a = 12 + fact(5)
print(a)
>>> 132

[Sve@r]

C'est un peu comme une variable qui se calculerait elle-même.

Bonjour

C'est le principe connu sous le nom de "récursivité". Ca permet à une fonction de s'appeler elle-même. L'appel se rebranche sur la même fonction mais dans un contexte différent. Et ensuite il attent la fin de ce sous-niveau pour continuer son calcul.
Mais si ce sous-niveau se réappelle lui-même, alors lui aussi génèrera un sous-sous niveau de travail et devra attendre la fin de ce 3° niveau avant de lui-même se terminer (tandis que le premier niveau attend toujours). Et etc.

L'exemple général qui illustre bien cette notion est effectivement le calcul de la factorielle où calculer fact(5) revient à calculer 5 * fact(4) ; mais où aussi calculer fact(4) revient à calculer 4 * fact(3). Et etc.

Un autre exemple est souvent montré avec la suite de Fibonacci où U1 et U2 sont fixés (généralement à 1 et 1) et ensuite quel que soit n, Un=U(n-2) + U(n-1). Ainsi calculer U(5) revient à calculer U(4) + U(3) ; mais calculer U(4) revient à calculer d'abord U(3) + U(2) et U(3) c'est U(2) + U(1). Et etc. Au final la suite donne 1, 1, 2, 3, 5 et donc U(5)=5.
D'où la confusion citée par Vins où tu as écrit "fib" en montrant un calcul de factorielle.

Accessoirement l'exemple de Fibonacci est surtout montré pour exposer le danger de la récursivité qui est peut-être simple à écrire (fib(x)=fib(x-2) + fib(x-1)) mais qui génére derrière une charge considérable pour l'ordi qui va calculer et recalculer inutilement certains termes un grand nombre de fois.