Si vous lisez cette ligne, c’est que vous n’avez pas encore compris :)
La récursivité
Partons du principe que vous avez triché et que vous n’avez pas suivi indéfiniment le lien un peu plus haut. En quelques mots, la récursivité est un procédé qui fait référence à lui-même. Vous avez pu vous en rendre compte un peu avant.
La récursivité permet donc d’exécuter plusieurs fois un même code, un peu comme les boucles. Et comme les boucles, il faut faire attention à garantir qu’on s’arrêtera un jour. Par exemple, le texte introductif de cet article n’a pas de condition d’arrêt, et il aurait fallu écrire juste avant “Si c’est la dixième fois que vous lisez ceci, ne considérez pas les deux lignes suivantes”.
On peut donc considérer qu’une fonction récursive f(x) est (en général) composée de deux grandes étapes, dans cet ordre :
- Vérification de la condition d’arrêt : Si l’objectif de l’algorithme est atteint, on arrête tout.
- Appel récursif : On appelle f avec un nouveau paramètre x’.
La récursivité est très souvent utilisée dans les algorithmes, car elle permet d’écrire les choses plus intuitivement (quand on y est habitué). Dans ce cours, vous rencontrerez quelques algorithmes récursifs, à commencer par le parcours en profondeur.
Pour l’heure, considérons l’exemple simple de la factorielle. Classiquement, on peut calculer n! de manière itérative de la manière suivante :
|
1 2 3 4 5 |
def fact (n) : result = 1 for i in range(2, n + 1) : result = result * i return result |
Le même algorithme, donné dans sa forme récursive, peut être écrit comme suit :
|
1 2 3 4 |
def fact (n) : if n == 0 : return 1 return n * fact(n - 1) |
Comme vous le voyez, n décroît strictement à chaque appel récursif. On garantit donc la terminaison de l’algorithme car à un moment on aura bien n = 0.
Récursivité terminale
Vous avez normalement lu l’article sur les files et les piles. Si vous avez lu la partie bleue, vous avez vu que les piles sont utilisées lors des appels de fonctions, et que les arguments ainsi que l’adresse de retour sont mis sur la pile lors d’un appel de fonction.
Les fonctions récursives ne sont pas différentes, et à chaque appel, la quantité d’information dans la pile augmente. Si la fonction s’appelle un trop grand nombre de fois, on risque alors un dépassement de pile, c’est à dire qu’on aura utilisé plus de mémoire que celle que l’OS aura attribué à la pile, et le programme plantera.
Une manière d’éviter cela est d’écrire des fonctions dites récursives terminales, c’est à dire que l’appel récursif est la toute dernière chose qui est faite dans la fonction. Pour de telles fonctions, quand l’exécution de f est terminée, on revient à l’appel de f précédent (grâce à l’adresse de retour), qui se termine immédiatement, et passe à l’appel de f précédent, etc. On stocke donc inutilement tout un tas d’adresses de retour, qui seront récupérées de la pile les unes après les autres.
Pour de nombreux langages de programmation, les appels de fonctions récursives terminales sont modifiés pour ne pas surcharger inutilement la pile. L’adresse de retour est donc mise en pile uniquement lors du tout premier appel à f, et lorsque f renverra le résultat, il n’y aura pas besoin de faire tout le chemin inverse.
Comme exemple, reprenons la fonction fact récursive donnée un peu plus haut. Cette fonction n’est pas récursive terminale, car lorsqu’on renverra 1 (via la condition d’arrêt), on le multipliera par 2, puis 3, …, puis n pour reconstruire le résultat à mesure qu’on reviendra des appels de fonctions.
Pour la transformer en fonction récursive terminale, on peut utiliser un accumulateur, c’est à dire une variable qu’on passera en paramètre lors de l’appel suivant à f. Voici un exemple de fonction factorielle récursive terminale :
|
1 2 3 4 5 6 7 8 9 10 11 |
# The recursive function, with the additional argument to make it terminal def factWithAccumulator (n, result) : if n == 0 : return result return factWithAccumulator(n - 1, n * result) ############################################### # The factorial function, initializing the accumulator def fact (n) : return factWithAccumulator(n, 1) |
En pratique, tous les langages de programmation n’ont pas cette optimisation, qui est généralement faite lors de la compilation (donc exit Python). C’est toutefois quelque chose de très important dans les langages dits fonctionnels (OCaml, Haskell…) dans lesquels la notion de boucle n’existe qu’à travers le mécanisme de récursion.
Bonjour, je voulais juste signaler un petit problème :
le lien en début de page (“cet article”) renvoie sur cette même page
ok fallait lire la suite
c’est cool ce truc de récursivité :)