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 automatique (sur la pile) s'applique de façon identique. Cependant, en l'absence de définitions récursives, chaque fonction a au plus un seul bloc d'activation en cours. Il en résulte que la pile d'exécution est bornée ; elle peut être allouée initialement et ne croît pas en cours d'exécution. Le programme opère par transformations de cette zone mémoire fixe. On dit que le programme 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 le principal reproche adressé aux programmes utilisant des définitions récursives : ils consomment de l'espace mémoire. Bien qu'automatique, la gestion de la pile prend aussi du temps. On dit que le programme est récursif.
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.