Récursivité terminale vers itération

1. Qu'est-ce que la récursivité terminale ?

Une fonction est dite récursive terminale (ou tail-recursive) si l'appel récursif est la toute dernière opération exécutée par la fonction. Il ne doit y avoir aucune opération en attente (multiplication, addition, etc.) qui serait effectuée sur la valeur de retour de l'appel récursif.

Prenons l'exemple classique de la fonction factorielle :

# Version non-terminale
def factorielle_non_terminale(n):
    if n < 2:
        return 1



    # Opération en attente : la multiplication par n
    return n * factorielle_non_terminale(n - 1) 

Ici, après le retour de factorielle_non_terminale(n - 1), il reste une multiplication à effectuer. L'appel n'est donc pas terminal. Chaque appel doit attendre le résultat du suivant, ce qui conduit à un empilement de contextes d'exécution dans la pile d'appels.

La vidéo suivante illustre parfaitement ce problème de consommation mémoire.

La technique de l'accumulateur

Pour transformer une fonction en version récursive terminale, la technique la plus courante est d'utiliser un paramètre supplémentaire appelé accumulateur. Cet accumulateur transporte le résultat partiel au fil des appels récursifs, éliminant ainsi le besoin d'opérations en attente.

# Version terminale avec un accumulateur
def factorielle_terminale(n, acc=1):
    if n < 2:
        return acc



    # L'appel récursif est la dernière action. Rien n'est fait avec son résultat.
    return factorielle_terminale(n - 1, acc * n)

Dans cette nouvelle version, le calcul acc * n est effectué avant l'appel récursif. Le résultat de cet appel est directement retourné, sans modification. L'appel est bien terminal.

La suite de la vidéo montre cette transformation.

Pour formaliser cette technique, je vous propose une lecture qui décrit la transformation en récursion terminale comme l'ajout d'une "fonctionnalité secrète" (le calcul via l'accumulateur) à la fonction.

2. La transformation mécanique en boucle while

Une fois qu'une fonction est sous forme récursive terminale, sa conversion en une fonction itérative devient purement mécanique. Un appel récursif terminal est conceptuellement équivalent à un GOTO (saut inconditionnel) qui met à jour ses paramètres. En programmation structurée, cela se traduit naturellement par une boucle while.

L'article de blog que vous venez de consulter propose une méthode simple en 5 étapes.

Résumons la méthode :

1. Étudier la fonction (et s'assurer qu'elle est récursive terminale).
2. Introduire une boucle infinie (while True:) autour du corps de la fonction.
3. Transformer l'appel récursif terminal en une mise à jour des paramètres et une instruction continue. Par exemple, return f(x-1, y+1) devient (x, y) = (x-1, y+1); continue.
4. Ajuster les cas de base pour qu'ils retournent la valeur finale (ils deviennent la condition de sortie de la boucle).
5. Nettoyer le code pour le rendre plus idiomatique (par exemple, transformer while True: if condition: break en while not condition:).

L'image suivante généralise ce patron de transformation. Une fonction récursive terminale de la forme F(x) = si P(x) alors G(x) sinon F(H(x)) est directement équivalente à une boucle while.

3. Analyse et justification : le "Pourquoi"

Pourquoi se donner la peine de cette transformation, surtout si la version récursive est plus simple à écrire ? La raison est la gestion de la mémoire, et plus précisément de la pile d'appels (call stack).

Chaque appel de fonction, récursif ou non, ajoute une "frame" (un contexte) sur la pile d'appels. Cette frame contient les paramètres de la fonction, ses variables locales, et l'adresse de retour.

• Dans une récursion non-terminale, chaque appel doit attendre que le suivant se termine. La pile grandit donc avec la profondeur de la récursion, consommant une mémoire proportionnelle à n (complexité spatiale en $O(n)$). Si n est grand, cela peut mener à une erreur de Stack Overflow.
• Dans une version itérative, il n'y a qu'un seul appel de fonction. La boucle s'exécute dans un seul contexte, utilisant une quantité de mémoire constante (complexité spatiale en $O(1)$).

Certains langages (notamment ceux de la famille fonctionnelle comme OCaml) implémentent une optimisation appelée Tail-Call Optimization (TCO). Le compilateur détecte la récursion terminale et la transforme automatiquement en une boucle, nous offrant le meilleur des deux mondes : un code lisible et une exécution efficace. Python n'implémente pas la TCO. Il est donc de votre responsabilité, en tant que programmeur, d'effectuer cette transformation manuellement lorsque la performance ou la profondeur de la récursion sont critiques.

La vidéo suivante visualise parfaitement la différence de consommation mémoire sur la pile d'appels.

4. Mise en pratique : Algorithme d'Euclide

Appliquons maintenant cette méthode à un autre algorithme fondamental : le calcul du plus grand commun diviseur (PGCD) par l'algorithme d'Euclide.

Voici sa définition récursive classique en Python :

def pgcd_rec(a, b):
    if b == 0:
        return a
    else:



        # L'appel est-il terminal ? Oui, car son résultat est directement retourné.
        return pgcd_rec(b, a % b)

Exercice :
En utilisant la méthode en 5 étapes, transformez la fonction pgcd_rec(a, b) en une fonction itérative pgcd_iter(a, b).

Prenez quelques minutes pour le faire sur papier ou dans un éditeur.