Python - Récursivité

La récursivité permet à une fonction de s'appeler. Les é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 utilisant la récursivité

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 à intégrer dans la liste avec l'index de début et de fin en entrée. Ensuite, la fonction de recherche binaire s'appelle elle-même jusqu'à trouver l'élément recherché ou conclut à son absence dans la liste.

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return None
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

2
None