Journal
RSS Feed
Tag cloud
C'est quoi la récursion terminale ?
Avant toute chose, nous devons parler de la pile d'exécution (ou "pile des appels", ou tout simplement "pile").
La pile d'exécution est un espace de stockage permettant d'enregistrer l'endroit où chaque fonction active (= les fonctions invoquées mais non terminées) doit retourner à la fin de son exécution. Elle enregistre donc des adresses, mais aussi le contexte des fonctions actives (les variables locales, les paramètres, etc.).
Le principe de la pile est le suivant: si une fonction A invoque une fonction B, alors on stocke A au sommet de la pile pour savoir où reprendre lorsque B sera terminée. Si B invoque une fonction C, B sera placé au sommet de la pile à son tour. A la fin de C, on récupère B au sommet de la pile, et à la fin de B on récupère A au sommet de la pile (d'où le terme de pile, car on y empile et on y dépile des éléments).
Alors, imaginons une factorielle naïve :
fact(n)
{
if(n == 1) // cas de base
return 1;
else
return n * fact(n - 1);
}
Décomposons notre fonction fact : pour calculer n * fact(n - 1), il est évidemment nécessaire de calculer fact(n - 1). Cela implique que fact(n) ne peut pas retourner de résultat sans d'abord obtenir le résultat de fact(n - 1). Avant d'exécuter fact(n - 1), on place donc fact(n) au sommet de la pile et on exécute fact(n - 1).
Sauf qu'évidemment, le problème se pose à nouveau : pour calculer fact(n - 1) on doit tout d'abord calculer fact(n - 2), et on place donc fact(n - 1) sur la pile. Et ainsi de suite jusqu'à ce que l'on atteigne fact(1) qui retourne immédiatement 1.
Le souci c'est que notre pile n'est pas infinie. Dans les langages classiques type C ou Java, elle est même ridiculement petite. Lorsqu'elle est pleine, le programme crashe car il n'est plus possible d'invoquer de nouvelle fonction : c'est le dépassement (ou débordement) de pile, stack overflow en anglais.
Une fonction récursive terminale, c'est tout simplement une fonction récursive particulière, où la récursion ne fait intervenir aucune autre opération que l'appel de la fonction. Ce qui, pour notre factorielle se traduit ainsi :
fact(n, total)
{
if(n == 0)
return total;
else
return fact(n - 1, total * (n - 1));
}
Ici, lorsque l'on arrive fact(n - 1, total * (n - 1)), il n'y a rien à sauvegarder. Il suffit donc simplement de remplacer fact(n, total) par fact(n - 1, total * (n - 1)) au sommet de la pile. L'espace nécessaire sur la pile pour exécuter fact(n, total) est donc constant, ce qui assure que la pile ne débordera pas, même pour un très grand nombre de récursion.
Hélas, cette optimisation n'est pas implicite et doit être effectuée à la compilation. Beaucoup de langages classiques ne le font pas (Java, C#, Python, C/C++ sauf avec l'option -foptimize-sibling-calls, etc.). Il s'agit donc principalement d'une propriété typique des langages fonctionnels car ceux ci font massivement appel à la récursion.
sam. 28 sept. 2013 11:19:25 CEST -
-
link
programmation récursion fonctionnel algorithmique
La pile d'exécution est un espace de stockage permettant d'enregistrer l'endroit où chaque fonction active (= les fonctions invoquées mais non terminées) doit retourner à la fin de son exécution. Elle enregistre donc des adresses, mais aussi le contexte des fonctions actives (les variables locales, les paramètres, etc.).
Le principe de la pile est le suivant: si une fonction A invoque une fonction B, alors on stocke A au sommet de la pile pour savoir où reprendre lorsque B sera terminée. Si B invoque une fonction C, B sera placé au sommet de la pile à son tour. A la fin de C, on récupère B au sommet de la pile, et à la fin de B on récupère A au sommet de la pile (d'où le terme de pile, car on y empile et on y dépile des éléments).
Alors, imaginons une factorielle naïve :
fact(n)
{
if(n == 1) // cas de base
return 1;
else
return n * fact(n - 1);
}
Décomposons notre fonction fact : pour calculer n * fact(n - 1), il est évidemment nécessaire de calculer fact(n - 1). Cela implique que fact(n) ne peut pas retourner de résultat sans d'abord obtenir le résultat de fact(n - 1). Avant d'exécuter fact(n - 1), on place donc fact(n) au sommet de la pile et on exécute fact(n - 1).
Sauf qu'évidemment, le problème se pose à nouveau : pour calculer fact(n - 1) on doit tout d'abord calculer fact(n - 2), et on place donc fact(n - 1) sur la pile. Et ainsi de suite jusqu'à ce que l'on atteigne fact(1) qui retourne immédiatement 1.
Le souci c'est que notre pile n'est pas infinie. Dans les langages classiques type C ou Java, elle est même ridiculement petite. Lorsqu'elle est pleine, le programme crashe car il n'est plus possible d'invoquer de nouvelle fonction : c'est le dépassement (ou débordement) de pile, stack overflow en anglais.
Une fonction récursive terminale, c'est tout simplement une fonction récursive particulière, où la récursion ne fait intervenir aucune autre opération que l'appel de la fonction. Ce qui, pour notre factorielle se traduit ainsi :
fact(n, total)
{
if(n == 0)
return total;
else
return fact(n - 1, total * (n - 1));
}
Ici, lorsque l'on arrive fact(n - 1, total * (n - 1)), il n'y a rien à sauvegarder. Il suffit donc simplement de remplacer fact(n, total) par fact(n - 1, total * (n - 1)) au sommet de la pile. L'espace nécessaire sur la pile pour exécuter fact(n, total) est donc constant, ce qui assure que la pile ne débordera pas, même pour un très grand nombre de récursion.
Hélas, cette optimisation n'est pas implicite et doit être effectuée à la compilation. Beaucoup de langages classiques ne le font pas (Java, C#, Python, C/C++ sauf avec l'option -foptimize-sibling-calls, etc.). Il s'agit donc principalement d'une propriété typique des langages fonctionnels car ceux ci font massivement appel à la récursion.
sam. 28 sept. 2013 11:19:25 CEST -
-
link
programmation récursion fonctionnel algorithmique
Ce journal est basé sur Ginger, un gestionnaire de lien minimaliste développé dans le cadre d'un stage de perfectionnement. Pour plus d'informations, consulter le wiki consacré à mes projets personnels.