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.

Parties du programme abordées

Contenus Capacités attendues Commentaires
Récursivité. Écrire un programme récursif. Analyser le fonctionnement d’un programme récursif. Des exemples relevant de domaines variés sont à privilégier.

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!.

4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120

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.

def factorielle(n):
    f = 1
    for i in range(n):
        f = f * (i + 1)
    return f

3) Testez cette fonction.

>>> factorielle(4)
24

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.

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)

5) Testez cette fonction.

>>> fact(4)
24

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.

mémoire 1 : n = 6
processus 1 : fact(6)
mémoire 2 : f = 1
mémoire 3 : i = 0
mémoire 2 : f = 1
mémoire 3 : i = 1
mémoire 2 : f = 2
mémoire 3 : i = 2
mémoire 2 : f = 6
mémoire 3 : i = 3
mémoire 2 : f = 24
mémoire 3 : i = 4
mémoire 2 : f = 120
mémoire 3 : i = 5
mémoire 2 : f = 740

On a utilisé 1 processus et 3 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.

mémoire 1 : n = 6
processus 1 : fact(6)
processus 2 : fact(5)
processus 3 : fact(4)
processus 4 : fact(3)
processus 5 : fact(2)
processus 6 : fact(1)

On a utilisé 6 processus et 1 mémoire.

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 ?

La méthode récursive risque de prendre beaucoup de place en mémoire car elle utilise n processus.

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.

fact(4) empile fact(4) 4*fact(3) empile fact(4) 4*fact(3) 3*fact(2) empile fact(4) 4*fact(3) 3*fact(2) 2*fact(1) dépile fact(4) 4*fact(3) 3*fact(2) 2*1 = 2 dépile fact(4) 4*fact(3) 3*2 = 6 dépile fact(4) 4*6 = 24 24 exécution du programme

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é.

La récursivité est généralement plus simple à programmer une fois qu'on a trouvé la bonne relation de récursion.
Par contre la consommation mémoire est généralement (beaucoup) plus importante que pour la programmation itérative.