Python - Recursión

La recursividad permite que una función se llame a sí misma. Los pasos fijos de código se ejecutan una y otra vez para nuevos valores. También tenemos que establecer criterios para decidir cuándo finaliza la llamada recursiva. En el siguiente ejemplo, vemos un enfoque recursivo de la búsqueda binaria. Tomamos una lista ordenada y damos su rango de índice como entrada a la función recursiva.

Búsqueda binaria usando recursividad

Implementamos el algoritmo de búsqueda binaria usando Python como se muestra a continuación. Usamos una lista ordenada de elementos y diseñamos una función recursiva para incluir la lista junto con el índice inicial y final como entrada. Luego, la función de búsqueda binaria se llama a sí misma hasta encontrar el elemento buscado o concluir sobre su ausencia en la lista.

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

Cuando se ejecuta el código anterior, produce el siguiente resultado:

2
None