Algorithme récursif

Un algorithme récursif est une recette qui permet de résoudre un problème en se répétant sur des sous-problèmes plus simples. C’est comme si on essayait de faire un puzzle, en commençant par faire les coins, puis les bords, puis le centre. On utilise la même recette pour chaque partie du puzzle, mais avec moins de pièces à chaque fois. On arrête la répétition quand on a plus de pièces à placer, ou quand on a fini le puzzle.

L’intelligence artificielle utilise cette recette pour résoudre des problèmes qui sont composés de sous-problèmes identiques ou similaires, comme le tri de listes, la recherche de mots, la génération de fractales, etc. Il existe différents types et méthodes de recettes, selon le type de problème à résoudre, le type de données à utiliser, et le type de solution à obtenir. Par exemple, il y a des recettes diviser pour régner, retour sur trace, programmation dynamique, etc.

Exemples :

Un exemple d’application de cette recette en intelligence artificielle est le tri fusion, qui permet de trier une liste de nombres dans l’ordre croissant. C’est comme si on voulait ranger des livres par ordre alphabétique, en commençant par couper la pile de livres en deux, puis en triant chaque moitié, puis en fusionnant les deux moitiés triées. On utilise la même recette pour chaque moitié de livres, mais avec moins de livres à chaque fois. On arrête la répétition quand on a plus qu’un livre, ou quand on a trié toute la pile.

Un autre exemple d’application de cette recette en intelligence artificielle est la recherche binaire, qui permet de chercher un nombre dans une liste de nombres triés. C’est comme si on voulait trouver un mot dans un dictionnaire, en commençant par regarder le mot du milieu, puis en comparant le mot cherché avec le mot du milieu, puis en continuant la recherche dans la moitié du dictionnaire qui contient le mot cherché. On utilise la même recette pour chaque moitié du dictionnaire, mais avec moins de mots à chaque fois. On arrête la répétition quand on a trouvé le mot, ou quand on a plus de mots à regarder.

Retourner à l'index du lexique