Pour résoudre algorithmiquement un problème, on dispose de différents types de boucles (loop en anglais) : « Pour » (for en anglais), « Tant que » (while), « Répéter jusqu’à ce que » (repeat until). Hélas, ces différentes structures ne sont pas toujours si faciles à mettre en œuvre. La condition de sortie de boucle dépend souvent de paramètres qui sont modifiés en cours d’exécution ; démontrer que cette condition va finir par être vraie n’est pas aisé. Pour les aficionados de la programmation fonctionnelle, la question ne se pose même pas, ils refusent les boucles : si l’on n’utilise pas de variables, à quoi bon itérer ?
Le remède à tous ces maux est la récursivité.
Un algorithme est récursif s’il s’appelle lui-même. Attention, tous les langages informatiques ne le permettent pas. L’exemple (tarte à la crème) de récursivité est le calcul de la factorielle : la factorielle d’un entier n (noté n!) est égale à n multiplié par la factorielle de n – 1. Comme il faut s’arrêter un jour, on fixe la factorielle de 1 à 1. Sur cet exemple, on voit qu’il y a deux règles à respecter lors de l’écriture d’une procédure récursive : il faut une condition de terminaison (ici c’est n = 1), et il faut réappliquer la procédure sur un « ensemble ...
Lire la suite