Récursivité
Un algorithme est dit récursif si l'expression qui le définit fait appel à l'algorithme lui-même.
Pour écrire un algorithme récursif, deux règles sont à respecter impérativement.
Le caractère récursif de certains algorithmes peut être caché par des appels à d'autres algorithmes. C'est le cas de la récursivité croisée dont le principe est qu'un algorithme f fasse appel à un autre algorithme g qui appelle lui-même f.
Plusieurs algorithmes peuvent satisfaire un problème donné. Si leurs comportements sont identiques en apparence (vus de l'extérieur), leurs mécanismes d'évaluation peuvent être différents, certains prenant plus de temps et nécessitant plus de mémoire de travail que d'autres.
Les algorithmes récursifs terminaux apparaissent comme plus économes en terme de nombre d'opérations et d'espace mémoire consommé.
