Algoritmos recursivos de busca linear e busca binária

Busca Linear Recursiva:

A complexidade desse algoritmo é O(n), onde n é o tamanho do vetor. A equação de recorrência para o caso médio é T(n) = T(n-1) + 1, e para o pior caso é T(n) = T(n-1) + 2, já que em cada chamada recursiva, a função faz uma comparação e uma adição ou subtração. Aplicando o método iterativo (árvore de recursão), temos:

Assim, a complexidade de busca linear recursiva é O(n).

Busca Binária Recursiva:

A complexidade desse algoritmo é O(log n), onde n é o tamanho do vetor. A equação de recorrência é T(n) = T(n/2) + 1, já que em cada chamada recursiva, o tamanho do vetor é dividido pela metade e é feita uma única comparação. Aplicando o método mestre, temos a = 1, b = 2 e d = 0, logo log a na base b é igual a d, e a complexidade é O(n^d log n) = O(log n).

Em resumo, a busca linear recursiva é menos eficiente do que a busca binária recursiva em grandes conjuntos de dados, já que a complexidade da busca linear é linear em relação ao tamanho do vetor, enquanto a complexidade da busca binária é logarítmica.

função busca_linear_recursiva(lista, valor, índice):
    se índice for igual ao comprimento da lista:
        retorne -1  // valor não encontrado
    se lista[índice] for igual a valor:
        retorne índice  // valor encontrado
    senão:
        retorne busca_linear_recursiva(lista, valor, índice + 1)

--------------------------------------- equacao ----------------------------------

T(n) = T(n-1) + c


------------------------------------------ java -------------------------------------

função buscaBinariaRecursiva(arr, inicio, fim, x)
    se fim >= inicio então
        meio = inicio + (fim - inicio) / 2
        se arr[meio] = x então
            retorne meio
        se arr[meio] > x então
            retorne buscaBinariaRecursiva(arr, inicio, meio-1, x)
        retorne buscaBinariaRecursiva(arr, meio+1, fim, x)
    retorne -1