La programmation récursive
La programmation récursive est un style de programmation dans lequel une fonction s'appelle elle-même !
Nous allons voir comment, en implémentant la fonction factorielle de manière récursive. Tu as déjà rencontré cette fonction dans le chapitre 4 En file indienne où tu l'as implémentée de manière itérative (avec une boucle). Voici un petit rappel de sa définition :
La factorielle d'un entier se calcule en faisant le produit . Par exemple . On note ce nombre et cette écriture se lit " factorielle".
Ce nombre représente combien de permutations sont possibles avec éléments. Par exemple un professeur veut faire un nouveau plan de classe. Il y a 20 élèves dans la classe. Combien de plans différents sont possibles ? Il y en a car c'est le nombre permutations possibles des élèves : 20 choix d'élève possibles pour la première place, fois 19 choix restants pour la seconde place, fois 18 choix restants pour la troisième place etc.
- 1
Comme on l'a dit en introduction, une fonction récursive s'appelle elle-même. Donc il y a un risque que ça ne finisse jamais ! Ce qui ferait planter le programme.
Pour éviter ça il faut s'assurer qu'il y ait une condition d'arrêt, comme pour les boucles. Dans notre cas la condition est
factorielle(1) = 1
. Lorsque l'argument est 1 alors on renvoie 1, sinon on fera un calcul récursif (dans la suite).
Pour commencer, définis dans l'éditeur une fonctionfactorielle
. Cette fonction prend un nombre en argument. Ajoute une instruction conditionnelle : si l'argument vaut 1 alors la fonction renvoie 1. On fera la suite dans la prochaine question.Solution
On définit la fonction
factorielle
qui prend un argument, par exemplen
. On ajoute ensuite la condition d'arrêt : sin
vaut 1 alors la fonction renvoie 1def factorielle(n): if n == 1: return 1
- 2
À présent supposons que l'argument soit supérieur à 1. Observe la formule de la factorielle et remarque qu'elle peut également s'écrire
Autrement dit, pour calculer la factorielle de on peut calculer la factorielle de et la multiplier par . Par exemple
Complète le corps de la fonctionfactorielle
: si l'argument n'est pas égal à 1 alors la fonctionfactorielle
renvoie le calcul ci-dessus, basé sur la factorielle du nombre précédent. Tu peux appeler la fonctionfactorielle
dans le corps de la fonctionfactorielle
, c'est le principe de la programmation récursive.Solution
On complète l'instruction conditionnelle lorsque
n
n'est pas égal à 1 : on fait l'appel récursif en renvoyant fois la factorielle dedef factorielle(n): if n == 1: return 1 else: return n * factorielle(n-1)
Observer que la fonction
factorielle
s'appelle elle-même, mais la condition d'arrêt limite le nombre d'appels. - 3
Combien y a-t-il de plans de classe possibles pour une classe de 20 élèves ? Appelle la fonction
factorielle
dans la console pour le savoir.Solution
On appelle la fonction
factorielle
dans la console :>>> factorielle(20) 2432902008176640000
Le nombre obtenu est énorme !