Contenu principal
Chapitre 6 · Projets › Leçon 4 sur 4

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

Ce nombre représente combien de permutations sont possibles avec nn é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!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. 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. 2

    À présent supposons que l'argument soit supérieur à 1. Observe la formule de la factorielle n!=n×(n1)××2×1n! =n\times (n-1)\times\cdots\times2\times1 et remarque qu'elle peut également s'écrire n!=n×(n1)!n! = n\times (n-1)!

    Autrement dit, pour calculer la factorielle de nn on peut calculer la factorielle de (n1)(n-1) et la multiplier par nn. Par exemple 3!=3×2!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 nn fois la factorielle de n1n-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. 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 !

Chargement...

Collecte des fichiers...

>>>