5. Récursivité

Exercice 55. Écrire une fonction calculant le PGCD d’une liste de nombres entiers naturels.Solution. Le programme se décompose en deux fonctions : une fonction de calcul du PGCD de deux entiers, et une fonction de calcul du PGCD d’une liste qui s’appuie sur la fonction précédente. Le procédé est simplement récursif.Lorsque la dernière instruction effectuée avant de quitter une procédure (ou une fonction) est un appel récursif isolé — la valeur de retour de l’appel ne pouvant constituer un argument pour un autre appel ou un calcul — à cette même procédure, on dit que la procédure est récursive terminale.
Comme illustration, nous calculerons récursivement (et naïvement !) de deux manières différentes la somme .
Dans tous les cas où n est non nul, la dernière instruction exécutée par la procédure somme( ) est une addition, dont l’un des termes est la valeur rendue par l’appel récursif de sommme( ). Le fait de quitter le corps de la fonction en terminant par une addition induit un empilement des termes avant de réaliser l’opération, c’est-à-dire un agrandissement de la pile.
Notre programme effectue la sommation de la manière suivante :
C’est-à-dire :
Selon les historiens, l’une des premières apparitions de la récursivité est la programmation du langage ALGOL60 par Edsger Dijkstra, lorsqu’il met en œuvre la notion de pile.
Si l’on songe au calcul de cette expression postfixée depuis une pile, on aura donc à évaluer la séquence :
Selon le principe consistant à dépiler deux opérandes puis empiler le résultat de l’opération, l’évaluation conduira à une hauteur maximale de pile égale à 12 dans notre exemple…