Récursion contre itération1#1

Il n'y a aucune différence de principe, du point de vue de l'exécution, entre des fonctions définies récursivement ou pas. Le mécanisme d'allocation sur la pile des cadres d'invocation s'applique de façon identique. Cependant, en l'absence de définitions récursives, chaque fonction a au plus un seul cadre d'invocation en cours. Il en résulte que la pile d'exécution est bornée ; elle pourrait être allouée initialement de sorte qu'elle ne croisse pas en cours d'exécution, le programme opérant par transformations de cette zone mémoire fixe. On dit d'un tel programme qu'il est itératif.

S'il existe des définitions récursives, la pile d'exécution n'est pas bornée, croissant et décroissant pendant l'exécution. C'est l'unique reproche adressé aux programmes utilisant des définitions récursives : ils consomment de l'espace mémoire, et bien qu'automatique, la gestion de la pile prend aussi du temps. Les programmeurs soucieux de l'efficacité de leurs programmes préfèrent donc les programmes itératifs, basés sur des structures d'itération. Ceux qui privilégient la facilité d'écriture et de compréhension des programmes n'hésitent pas à écrire des programmes récursifs.