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 $n$ se calcule en faisant le produit $n\times (n-1)\times\cdots\times2\times1$ . Par exemple $3! = 3\times2\times1=6$ . On note ce nombre $n!$ et cette écriture se lit " $n$ factorielle".

Ce nombre représente combien de permutations sont possibles avec $n$ é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 $20!$ 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 fonction factorielle. 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 exemple n. On ajoute ensuite la condition d'arrêt : si n vaut 1 alors la fonction renvoie 1
```
def factorielle(n):
	if n == 1:
		return 1
```
2
À présent supposons que l'argument soit supérieur à 1. Observe la formule de la factorielle $n! =n\times (n-1)\times\cdots\times2\times1$ et remarque qu'elle peut également s'écrire $n! = n\times (n-1)!$

Autrement dit, pour calculer la factorielle de $n$ on peut calculer la factorielle de $(n-1)$ et la multiplier par $n$ . Par exemple $3! = 3\times 2!$

Complète le corps de la fonction factorielle : si l'argument n'est pas égal à 1 alors la fonction factorielle renvoie le calcul ci-dessus, basé sur la factorielle du nombre précédent. Tu peux appeler la fonction factorielle dans le corps de la fonction factorielle, 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 $n$ fois la factorielle de $n-1$
```
def 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 !