Récursion
La récursion est gourmande en pile. Sachant que la taille est défaut est de 1 Mo, il est facile d'atteindre la saturation. Thread Stack Size Archive du 31/05/2018 le 21/06/2020
Tail Call Optimization
Tous les algorithmes peuvent s'écrire soit sous forme de boucle (nécessite des données mutables), soit sous forme de récursion (l'immuabilité des données est à la discrétion de l'implémentation).
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).
Le TCO est actif lorsque le return fait appel à lui-même.
- 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 et rien d'autre après.
Tail Call Optimization in C++ Archive du 23/12/2018 le 16/06/2020
- Exemple non compatible avec LTO.
L'implémentation ci-dessous ne pourrait ne pas 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); }