Récursion

La récursion permet à une fonction de s'appeler elle-même. Des étapes fixes du code sont exécutées encore et encore pour de nouvelles valeurs. Nous devons également définir des critères pour décider de la fin de l'appel récursif. Dans l'exemple ci-dessous, nous voyons une approche récursive de la recherche binaire. Nous prenons une liste triée et donnons sa plage d'index comme entrée à la fonction récursive.

Recherche binaire par récursion

Nous implémentons l'algorithme de recherche binaire en utilisant Python comme indiqué ci-dessous. Nous utilisons une liste ordonnée d'éléments et concevons une fonction récursive qui prend en entrée la liste ainsi que l'indice de début et de fin. Ensuite, la fonction de recherche binaire s'appelle elle-même jusqu'à ce qu'elle trouve l'élément recherché ou conclut à son absence dans la liste.

Exemple