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 ... Lire la suite