LG

La récursion est gourmande en pile. Sachant que la taille est défaut est de 1 Mo sous Windows et 8 Mo sous Linux, il est facile d'atteindre la saturation. Thread Stack Size Archive du 31/05/2018 le 21/06/2020

Tous les algorithmes peuvent s'écrire soit sous forme d'une boucle (nécessite des données mutables), soit sous forme d'une récursion (immuabilité des données possible).

L'objectif du TCO est de convertir automatiquement une récursion (qui augmente la taille de la pile) en un jmp (qui n'incrémente pas la taille de la pile).

Cette optimisation ne se fait qu'en release :

1. clang utilise call en -O0 et jne pour -O1, -O2, -O3, -Os, -Oz, -Og, -O, -O4,
2. gcc utilise call en -O0, -O1, -Og et jne pour -O2, -03, -Os, -Oz,
3. msvc utilise call en /O1, /Ob, /Od, /Oi, /Os, /Ot, /Oy et jmp en /O2, /Ox.

• Exemple compatible avec TCO

int factorial_accumulate(int n, int accum)
{
  if (n == 1)
    // Absence de récursion.
    return accum;
  else
    // Récursion.
    // Mais comme il s'agit de la dernière opération de la fonction,
    // le TCO va privilégier une instruction jmp à un call.
    return factorial_accumulate(n - 1, n * accum);
}
 
int factorial(int n)
{
  return factorial_accumulate(n, 1);
}

Mais attention, il faut que le return fasse uniquement appel à la fonction de récursion.

Tail Call Optimization in C++ Archive du 23/12/2018 le 16/06/2020

• Exemple non compatible avec LTO.

L'implémentation ci-dessous pourrait ne pas être optimisée par le LTO. GCC 10, clang 10 optimise à partir de -O2 mais Visual Studio 2019 n'optimise pas à /O2.

int factorial(int n)
{
  if (n == 1)
    return 1;
  else
    // On fait une multiplication en plus de l'appel à la fonction factorial.
    return n * factorial(n - 1);
}

Tail Call Optimization Archive du 10/11/2006 le 16/06/2020