Résumé du chapitre 15
La constitution de cet algorithme nécessite l'établissement d'un invariant qui, comme son nom l'indique, est une propriété du calcul qui reste toujours vrai au cours de celui-ci. L'invariant permet également de prouver la correction de l'algorithme.
On peut construire le programme itératif à partir de la version naïve en ajoutant des paramètres permettant la mémorisation d'étapes intermédiaires du calcul, le principe étant de transférer les calculs non terminaux vers ces paramètres.
L'algorithme itératif est plus performant que le récursif, parfois en temps, touours en espace. Ces différences sont dues à un calcul de ``haut en bas'' de l'itératif plutôt que ``bas en haut'' du récursif.
