Je lis le cours "Découvrez le fonctionnement des algorithmes" dans la partie "Voyez le monde autrement avec la récursivité" (https://openclassrooms.com/fr/courses/4366701-decouvrez-le-fonctionnement-des-algorithmes/4385343-voyez-le-monde-autrement-avec-la-recursivite#/id/video_Player_1)
Je coince sur le déroulement de la récursivité à cette étape : https://openclassrooms.com/fr/courses/4366701-decouvrez-le-fonctionnement-des-algorithmes/4385343-voyez-le-monde-autrement-avec-la-recursivite#/id/r-4385256.
Voici le code de cette étape :
def fibo(n):
if n <= 1:
return 1
else:
return fibo(n-1) + fibo(n-2)
Je ne sais pas si je fais `fibo(5)` comment il fait pour me trouver 8 ? Comment il additionne ?
Pouvez-vous m'aider à voir un peu plus clair s'il vous plaît ?
Je réessaye à la main et de refaire un print mais là où je ne comprends pas c'est quand tu appelles `fibo(n-1)`. Par exemple `fibo(5-1)` dans le cas de la récursivité il va s'appeler lui même et faire `fibo(4-1) + fibo(4-2)` ?
Je vais réessayer mais je ne comprends pas quand même comment fonctionne les calculs à la fin ^^'
PS : Oui je pense être dans le bon endroit car c'est d'un point de vue algo et non d'un point de vue langage de programmation
C'est trompeur. Il faut éclaircir qui est ce "il".
Quand un bout de code exécute résultat = fib(5), c'est le _déroulement_ de fib(5) qui fait appel au déroulement de fib(4) et à celui de fib(3). Il ne s'appelle pas lui-même.
Techniquement, ce déroulement, c'est du code, et aussi les données à qui on l'applique. Alors ok, le code de la fonction contient des appels à la même fonction. Et alors ?
Pour manger un repas, tu manges une entrée, tu manges un plat, et tu manges un dessert. Et manger le repas, c'est faire les trois dans l'ordre.
Dans le cas de fibonacci, quand on voit fibo(n-1)+fibo(n-2), normalement on ne devrait pas demander si il y a une addition, parce que ça se voit. Tu dois avoir un souci avec un autre aspect. Sans doute l'aspect fonctionnel : on décrit un traitement sous forme d'une fonction qui calcule un résultat, et ne s'occupe pas d'afficher, lire, etc.
Choisir fibonacci comme exemple introductif, ça montre un manque d'imagination de la part de rédacteur du cours. Et un décalage avec le public visé, qu'on ne peut plus supposer familier avec ce genre de chose (les suites définies par recurrence). Et si on choisit un exemple X pour illustrer la notion Y, c'est quand même mieux que tout le monde connaisse X avant. Sinon ça ne fait qu'embrouiller.
Je ne sais pas de quel cours il est question. On aurait pu choisir des exemples plus simples:
def somme(n): # somme de 1 à n
if n < 1:
return 0
return n + somme(n-1)
def facto(n): # n factorielle
if n < 1:
return 1
return n * facto(n-1)
def stupid(n): # récursivité infinie
return stupid(n-1)
Il me semble que les deux règles de la récursivité sont:
+ que la fonction s'appelle elle-même avec un paramètre identique ou différent
+ qu'il existe une règle pour mettre fin à ces appels récursifs.
+ ... que ça ait du sens ...
-
La fonction fibo() s'appelle effectivement "elle-même" mais avec des arguments différents.
La définition (X) de la suite de Fibonacci est que chaque terme de la suite est la somme des deux termes précédents de cette suite.
Et le code (Y) exprime bien cette propriété.
Sauf que dans la théorie, le premier terme est 0 et le deuxième terme est 1. Il n'y a pas de terme -1 ou -2.
Ce qui n'est pas le cas dans le code (Y). Le code suivant serait plus conforme avec la théorie:
def fibo(n):
if n <= 1:
return 0
if n == 2:
return 1
return fibo(n-2) + fibo(n-1)
- Edité par PierrotLeFou 7 août 2020 à 17:56:21
Le Tout est souvent plus grand que la somme de ses parties.
Le fonctionnement des algorithmes - Récursivité
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.