Python - recursão

A recursão permite que uma função chame a si mesma. Etapas fixas de código são executadas repetidamente para novos valores. Também temos que definir critérios para decidir quando a chamada recursiva termina. No exemplo a seguir, vemos uma abordagem recursiva para a pesquisa binária. Pegamos uma lista classificada e fornecemos seu intervalo de índice como entrada para a função recursiva.

Pesquisa binária usando recursão

Implementamos o algoritmo de pesquisa binária usando python, conforme mostrado abaixo. Usamos uma lista ordenada de itens e projetamos uma função recursiva para incluir na lista junto com o índice inicial e final como entrada. Em seguida, a função de busca binária chama a si mesma até encontrar o item procurado ou conclui sobre sua ausência na 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))

Quando o código acima é executado, ele produz o seguinte resultado -

2
None