Chapitre 1 : Programmation - Récursivité

I. Introduction.

En classe de 1ère, les programmes sont écrits avec des boucles et des affectations. On donne une suite d'instructions qui modifient un état (variables, mémoire). Ce style de programmation est dit paradigme impératif (les séquences d'instructions sont exécutées les unes après les autres).

Dans ce paradigme, on utilise une technique de résolution des problèmes dite itérative (itérer c'est répéter n fois un processus en faisant changer la valeur des variables jusqu'à obtention du résultat, les instructions sont exécutées dans des boucles).

Nous verrons d'autres paradigmes de programmation peu à peu dans l'année mais pour l'instant nous allons continuer à programmer en utilisant la programmation impérative, mais en voyant autre chose que l'itératif : la technique du récursif.

Cette technique est basée sur une fonction qui s'appelle elle-même. On l'utilise dans le paradigme impératif mais pas seulement.

Les termes "récursif", "récursion" et "récursivité" ont la même racine latine que "récurrence" : currere = courir, et recurrere = courir en arrière (qui a donné également recourir, recours = action de faire appel en justice).

Le terme récurrence apparaît avec Poincaré au tout début du 20ᵉ siècle. On parle dès lors de formule de récurrence (vu en 1ère avec les suites), et de raisonnement par récurrence (vu en terminale). La "récursivité" n'apparaît dans le Larousse qu'en 1968, avec les progrès de l'informatique.

II. Principes de la récursivité.

1. Définition et exemples.

Définition : En informatique, une fonction f est appelée fonction récursive quand la définition de f utilise des valeurs de f, c'est-à-dire qu'une fonction récursive est une fonction qui s'appelle elle-même.

On trouve des définitions récursives dans de nombreux domaines, comme par exemple :

Dictionnaire : chaque mot du dictionnaire est défini par d'autres mots, eux-mêmes définis par d'autres mots dans ce même dictionnaire.
Image contenant une image similaire, ou caméra qui filme devant un miroir.
Mathématiques : suites définies par récurrence, fractales.

Exemple 1 :

#avec une fonction itérative (une boucle) :
def fct(debut, fin):
    for i in range(debut, fin + 1):
        print(i)
fct(0, 3)

Résultat :

#avec une fonction récursive :
def fct(debut, fin):
    if debut <= fin:
        print(debut)
        fct(debut + 1, fin)   #la fonction s'appelle elle-même
fct(0, 3)  #on appelle la fonction

Résultat :

La fonction fct est appelée avec les paramètres 0 et 3 et bien sûr, 0 <= 3 donc on affiche 0 et on appelle la fonction fct(1, 3), comme 1 <= 3, on affiche 1 et on appelle fct(2, 3) et 2 <= 3 donc on affiche 2 et on appelle fct(3, 3) et 3 <= 3 donc on affiche 3 et on appelle fct(4, 3), mais cette fois 4 > 3 donc rien n'est affiché, c'est terminé.

On remarque que dans cet exemple, on n'a plus besoin de la boucle for.

La ligne if debut <= fin: est la condition d'arrêt : dès que debut devient strictement supérieur à fin, la fonction s'arrête.

Exemple 2 : Un grand classique : le calcul de la factorielle d'un entier naturel.

En mathématiques, la fonction factorielle est définie pour tout entier naturel n par n! = 1 × 2 × ... × (n-1) × n (on peut préciser que 0! = 1).

Par exemple : 6! = 1 × 2 × 3 × ... × 6 = 720.

On peut donc programmer cette fonction en itératif :

#factorielle itératif
def fact_it(n):
    f = 1
    for i in range(2, n + 1):
        f = f * i
    return f

print(fact_it(6))

Résultat :

On remarque qu'on a dû utiliser 2 variables locales, f et i, pour faire le calcul demandé.

Mais on peut aussi définir la fonction factorielle par une relation de récurrence :

n! = 1 si n = 0, et sinon n! = n × (n-1)!

On peut alors facilement définir la fonction factorielle en récursif, en reprenant quasiment mot pour mot cette dernière définition :

def factorielle(n):
    if n == 0:  # condition d'arrêt
        return 1
    return n * factorielle(n - 1)   #la fonction factorielle s'appelle elle-même

print(factorielle(6))

Résultat :

Cette fois, on n'a utilisé aucune variable locale, aucune itération n'a été faite.

On distingue clairement deux cas dans cette fonction :

le cas n = 0, appelé cas d'arrêt (ou cas terminal), il garantit l'arrêt de l'algorithme ;
le cas n > 0, qui produit un appel récursif à la fonction factorielle.

Attention : Dans une implémentation récursive, il y a toujours une condition qui permet de stopper la récursion : ici cette condition est n = 0.

2. La pile d'exécution.

Pile d'exécution (ou pile d'appels, call stack en anglais) : structure de données qui sert à enregistrer des informations au sujet des fonctions actives dans un programme. Son utilisation principale est de garder la trace de l'endroit où chaque fonction active doit retourner à la fin de son exécution.

En pratique, lorsqu'une fonction est appelée par un programme, son adresse de retour (adresse de l'instruction qui suit l'appel) est empilée sur la pile d'appels. En plus d'emmagasiner des adresses de retour, la pile d'exécution stocke aussi d'autres valeurs, comme les variables locales de la fonction, les paramètres de la fonction, etc.

On parle de pile, car les exécutions successives "s'empilent" les unes sur les autres. Nous verrons plus tard dans l'année, plus en détail, cette structure de données ; pour l'instant il suffit de voir cette pile comme, par exemple, une pile d'assiettes. Si on ajoute une assiette sur la pile (on dit qu'on l'empile), la première qu'on peut retirer (on dit qu'on la dépile) est la dernière qui a été posée sur la pile : c'est le principe du "dernier arrivé, premier sorti" (ou "last in, first out" en anglais).

Tout appel à une fonction crée 2 entrées en mémoire :

1 pour stocker l'argument, qu'on note x ;
1 pour stocker le résultat, qu'on note y.

Si le calcul de y n'est pas encore possible, ce qui est le cas s'il y a un appel récursif, le couple (x, y) est empilé et la pile augmente ainsi tant qu'il y a des calculs en attente. Lors de l'appel d'une fonction récursive, chaque appel récursif conduit à un nouvel empilement dans la pile d'exécution.

Dès qu'un calcul de y est possible, (x, y) est dépilé ; on récupère y, et on utilise sa valeur pour faire le calcul qui est en attente au sommet de la pile. Dans le cas d'une fonction récursive, cela se produit quand on arrive à la condition d'arrêt.

Quand la pile est vide, le dernier y qui a été dépilé fournit le résultat. La récursion s'arrête quand on dépile l'élément correspondant au 1er appel de la fonction.

Par exemple, pour calculer 5! en utilisant la fonction récursive factorielle :

Remarque : On voit que le nombre d'appels imbriqués réalisés par une fonction récursive peut être important, et il faut stocker ces appels, ce qui est coûteux en mémoire. En Python, par défaut, il est impossible de dépasser un certain nombre d'appels récursifs pour éviter de saturer complètement la mémoire. On peut connaître ce nombre et même le changer à l'aide du module sys.

import sys
sys.getrecursionlimit()   #donne la limite actuelle de récursion (profondeur max de la pile)

sys.setrecursionlimit(5000)   #permet de modifier la limite de récursion

sys.getrecursionlimit()

3. Principes généraux et remarques.

Une fonction récursive doit impérativement contenir une ou plusieurs conditions d'arrêt, sinon le programme va boucler jusqu'à ce que la pile soit remplie et renvoyer une erreur.

Les valeurs passées en paramètres dans les appels récursifs doivent changer à chaque appel, sinon la fonction s'exécutera toujours de manière identique et la condition d'arrêt ne pourra jamais être vérifiée.

On doit être sûr qu'après un certain nombre d'appels, la ou les valeurs passées en paramètres vont permettre de satisfaire la ou les conditions d'arrêt.

Exemple :

import sys
sys.setrecursionlimit(100)
def f(i):
    return f(i)
print(f(2))

Résultat :

---------------------------------------------------------------------------
RecursionError                           Traceback (most recent call last)
<ipython-input-1-...> in <module>
      3 def f(i):
      4     return f(i)
----> 5 print(f(2))

... (95 appels récursifs imbriqués supplémentaires) ...

RecursionError: maximum recursion depth exceeded

La fonction f s'appelle elle-même indéfiniment avec le même paramètre i : il n'y a pas de condition d'arrêt, la pile finit donc par être remplie (ici, dès que la limite fixée à 100 est atteinte) et Python interrompt le programme.

Pour écrire un algorithme récursif résolvant un problème X appliqué à un objet N, on dégage les deux éléments suivants :

le sous-problème : on identifie le même problème que le problème X mais appliqué à un objet M de « taille » inférieure et dont la résolution permet de résoudre le problème X appliqué à l'objet N. Ce sous-problème peut souvent être décrit par une relation de récurrence.
le cas de base : on isole le cas du problème X appliqué à un objet de taille telle que le problème X ne peut être ramené à un sous-problème ; il s'agit en quelque sorte d'un cas irréductible. C'est ce cas qui va servir de cas d'arrêt.

Remarques :

L'usage de la récursivité présente des avantages dans certaines situations (formulation simple) mais aussi des inconvénients !

Stocker systématiquement l'état d'une fonction avant chaque appel récursif dans la pile d'appels n'est pas gratuit, en temps comme en mémoire. De plus, il faut faire attention à ce que les appels récursifs ne se chevauchent pas, et prendre garde à ne pas faire un trop grand nombre d'appels récursifs imbriqués, sinon d'une part la complexité va exploser, mais aussi la pile d'exécution risque d'être rapidement pleine.

La programmation récursive n'est jamais indispensable. Les algorithmes récursifs peuvent toujours être mis sous une forme itérative en utilisant intelligemment des boucles for ou while. Toutefois la programmation récursive s'impose d'elle-même dans certaines situations et elle permet parfois de minimiser de manière importante le nombre d'opérations. D'une manière générale, si pour un problème donné une formulation itérative s'obtient facilement, il est préférable de l'utiliser.

Dernier point : même si nous ne le ferons pas de manière formelle, le problème de la terminaison de la récursion doit être examiné. Même s'il est parfois délicat de la prouver, elle nécessite en général de raisonner par récurrence.