Un programme informatique est dit récursif s'il demande sa propre exécution au cours de son déroulement. Sans aucun exemple, cette phrase est difficile à comprendre… et il est encore plus difficile de saisir pourquoi aujourd'hui les langages de programmation utilisent tous la récursivité alors que les premiers, comme Cobol, pour la gestion, ou Fortran, pour le calcul scientifique, s'en passaient. L'une des raisons est la sûreté des programmes récursifs, pratiquement les seuls dont on puisse démontrer qu'ils font bien ce qu'ils sont censés faire…
Récurrence et jeux de cartes
Prenez un jeu de cartes, mélangez-le puis essayez de le trier. Comment faire ? A priori, la tâche est complexe. Le principe de récurrence permet de la simplifier considérablement en posant la question autrement : imaginez que vous sachiez trier n cartes, comment en trier n + 1 ? Plus prosaïquement, vous savez trier un jeu de quatre cartes. On vous en donne une de plus ; que faites-vous ?
Bien entendu, vous triez les quatre premières puis insérez la cinquième à sa place. Pour cela, il suffit de la comparer successivement avec les cartes déjà triées en commençant par la première. Ici, la nouvelle carte s'insère après la deuxième. Cette méthode repose exactement sur l'idée de récurrence ! Pour vous en convaincre, formalisons-la dans le style des démonstrations par récurrence. Voici donc une méthode qui, pour la donnée d'un jeu de cartes T, renvoie le même jeu trié :
