Cours d'informatique pour le lycée

Récursivité

Un algorithme (ou une fonction) récursif est un algorithme qui fait appel à lui-même dans sa définition.

Exemple de factorielle

Définition

Factorielle est une opération mathématique notée avec un point d'exclamation : n!. On dira « factorielle n » ou « n factoriel ». La factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Par convention 0! = 1.

On a donc 1! = 1, 2! = 2 x 1 = 2, 3! = 3 x 2 x 1 = 6,…

1) Écrivez et calculez 4! et 5!.

Programmation itérative

On parle de programmation itérative par opposition à la programmation récursive. C'est la méthode que vous avez l'habitude d'utiliser.

2) Proposez une fonction en Python qui permette de calculer n!. Il y aura une boucle for.

3) Testez cette fonction.

Programmation récursive

On peut remarquer que n! = n x (n-1)!. Cela ressemble beaucoup à la définition d'un algorithme récursif. Pour que la récursion ne soit pas infinie il doit y avoir un cas d'arrêt. Ici le cas d'arrêt est 1! = 1.

4) Proposez une fonction récursive en Python qui permette de calculer n!. Il y aura un if … else.

5) Testez cette fonction.

Inconvénient de la récursivité

Pour voir simplement l'inconvénient principal de la récursivité, nous allons calculer ensemble 6! avec les deux méthodes. Voilà comment nous allons procéder :

5) Commencez par la méthode itérative et donnez le nombre de processus utilisés ainsi que le nombre de mémoires.

6) Refaire le calcul de 6! avec la méthode récursive et donnez le nombre de processus utilisés ainsi que le nombre de mémoires.

7) Sachant qu'un processus prend également de la place en mémoire, quelle méthode risque de prendre énormément de place en mémoire si on calcule la factorielle d'un grand nombre ?

Analyse du fonctionnement

On analyse en général le fonctionnement d'un programme récursif en faisant un empilement et un dépilement des appels à la fonction.

8) Effectuez ce travail pour 4! avec le professeur.

Bilan sur la récursivité

La récursivité est en général caractérisée par deux éléments :

variable de contrôle
souvent un entier qui décroit à chaque appel de la fonction et qui entraine la fonction vers un cas de base ;

cas de base
cas pour lequel on connait le résultat.

9) Faites le bilan avec le professeur des avantages et inconvénients de la récursivité.