LG

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====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. [[https://docs.microsoft.com/en-us/windows/win32/procthread/thread-stack-size|Thread Stack Size]] {{ :lang:c:fonctions:thread_stack_size_-_win32_apps_microsoft_docs_2020-06-21_09_53_20_.html |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''

<code c>
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);
}
</code>

Mais attention, il faut que le ''return'' fasse uniquement appel à la fonction de récursion et rien d'autre après.

[[https://medium.com/software-design/tail-call-optimization-in-c-829b4b257c9a|Tail Call Optimization in C++]] {{ :lang:c:fonctions:tail_call_optimization_in_c_-_software_design_-_medium_2020-06-16_4_28_30_pm_.html |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''.

<code c>
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);
}
</code>

[[https://wiki.c2.com/?TailCallOptimization|Tail Call Optimization]] {{ :lang:c:fonctions:tail_call_optimization_2020-06-16_3_38_54_pm_.html |Archive du 10/11/2006 le 16/06/2020}}