Python - Ricorsione

La ricorsione consente a una funzione di chiamare se stessa. I passaggi fissi del codice vengono eseguiti ancora e ancora per nuovi valori. Dobbiamo anche stabilire i criteri per decidere quando termina la chiamata ricorsiva. Nell'esempio seguente vediamo un approccio ricorsivo alla ricerca binaria. Prendiamo un elenco ordinato e forniamo il suo intervallo di indice come input per la funzione ricorsiva.

Ricerca binaria utilizzando la ricorsione

Implementiamo l'algoritmo di ricerca binaria utilizzando Python come mostrato di seguito. Usiamo un elenco ordinato di elementi e progettiamo una funzione ricorsiva da inserire nell'elenco insieme all'indice iniziale e finale come input. Quindi la funzione di ricerca binaria chiama se stessa fino a trovare l'elemento cercato o conclude sulla sua assenza nell'elenco.

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))

Quando il codice sopra viene eseguito, produce il seguente risultato:

2
None