[Informatique] La dérecursivation

Contexte

Les fonctions récursives et les boucles ont le même rôle dans un programme: répéter un bloc d'instruction jusqu'à qu'une condition soit remplie.

Il y a néanmoins une différence de taille entre les deux. Une fonction possède son propre contexte, c'est à dire un morceau de mémoire qui lui est propre et qui contiens ses arguments, ses variables, un pointeur qui désigne la fin du contexte et un pointeur de retour utilisée à la fin de la fonction. Le contexte se trouve sur la pile du programme, une zone de la mémoire utilisée comme pile pour l'allocation et la désallocation de la mémoire. Une variable de deux appels différents de la même fonction auront donc des adresses mémoires différentes.

Même si c'est très utile dans certains cas, une fonction récursive occupe un espace mémoire qui dépend du nombre d'appels, alors qu'une boucle occupe un espace mémoire constant. Même si ce n'est pas gênant d'un point de vue théorique (une machine de Turing possède un espace mémoire infini), c'est un peu plus problématique dans la réalité.

Ainsi, la fonction suivante provoquera un plantage par manque de mémoire au bout d'un temps (très long) à cause des deux pointeurs utilisés a chaque appel alors qu'elle semble parfaitement "saine":

Code:

void function a(){
    a();
}

De plus, même si la mécanique de la pile rend les allocations et désallocations des fonctions très rapides (une addition/soustraction sur le pointeur de pile), il s'agit tout de même de calculs en plus. Enfin, à la fin d'un appel récursif, le programme doit suivre le pointeur de retour pour sortir de la fonction et ce a chaque appel de la fonction récursive.

Si on compare les deux codes suivants:

Code:

for(int i = 0; i < 100; i++){
}

Code:

void function b (int i){
    if(i < 100) b(i+1) ;
}

La boucle for fait une allocation, 100 additions, 100 copies (le "i++" additionne ET copie), 100 comparaisons et 100 sauts.
La fonction fait 300 additions (100 pour le pointeur de pile, 100 pour la ligne "i+1" et 100 pour le calcul du contexte), 100 soustractions (pour le pointeur de pile), 100 comparaisons, 100 copies d'entier et 200 sauts (100 a l'appel et 100 au return).

Ai-je besoin de dire laquelle est la plus rapide ?

Heureusement pour la programmation fonctionnelle, il existe une technique appelée la dérecursivation qui transforme certaines fonctions récursives (les terminales) en boucles. De nos jours, cette transformation est faite automatiquement et silencieusement par tout compilateur digne de ce nom.

Fonction récursive terminale (tail-recursive function)

Une fonction récursive terminale est une fonction dont les appels récursifs se font a la fin de la fonction. Plus spécifiquement, il n'y a aucun code qui s'exécute entre l'appel et le retour de la fonction. Dans le cas d'une fonction récursive terminale, le contexte n'a plus aucune utilité: on ne relit plus les variables après le retour de l'appel récursif (et ce pour TOUS les appels de la fonction). Il est donc possible de désalloué les variables juste avant le saut sans que cela ne change le sens de la fonction.

La détection d'une fonction récursive terminale n'est pas une opération triviale car elle implique d'étudier les conditions du code, mais comme c'est quelque-chose qu'on fait au moment de la compilation... on s'en fiche un peu du temps de calcul.

Dérecursivation

L'algo de dérecursivation est trivial: contrairement à une fonction normale, le compilateur ne construit le contexte qu'au premier appel. Ensuite, il ne modifie aucun des 3 pointeurs (pointeur de pile, pointeur de retour et pointeur de contexte) et se contente de recopier les arguments. En d'autres termes, il réutilise l'espace mémoire du contexte de l'appel précédent. Comme une variable ne doit jamais être lu avant d'être initialisée et qu'elle n'est jamais réutilisée entre l'appel récursif et le retour, il n'y a aucune différence entre une fonction récursive normale et une fonction dérecursivée.
En bonus, comme le pointeur de retour n'est pas modifié d'un appel sur l'autre, la fonction n'a qu'un saut à faire pour sortir complètement du calcul indépendamment de la profondeur du calcul récursif.

La seule différence qui reste entre une fonction dérecursivée et une boucle se trouve dans la première création de contexte. Dans une fonction dérecursivée, il y a une copie des variables d'entrée.