A busca sequencial é um algoritmo simples que verifica cada elemento de um vetor até encontrar o elemento desejado ou percorrer todos os elementos.
Formalmente, dado um vetor v[0 . . n-1] de tamanho n e um elemento x a ser buscado, o algoritmo percorre as posições i=0,1,2, \ldots, n-1 comparando v[i] com x. Se encontrar x, retorna o índice i onde foi encontrado; caso contrário, retorna um valor indicando que x não está presente (por exemplo, -1 ).
Escreva uma versão recursiva do algoritmo de busca sequencial.

Passo 1

O enunciado pede: escrever uma versão recursiva da busca sequencial. As informações dadas e o que é esperado são:
  • Há um vetor v[0 \ldots n-1] de tamanho n.
  • Há um elemento alvo x que queremos encontrar no vetor.
  • O algoritmo deve percorrer as posições i=0,1,\dots,n-1 comparando v[i] com x.
  • Se encontrar x, deve retornar o índice i onde foi encontrado; caso contrário, retornar um valor indicando “não encontrado” (por exemplo -1).
  • A implementação pedida é a versão recursiva do algoritmo descrito.

Passo 2

Entendendo recursão (aula rápida e prática).
  • Ideia: uma função recursiva resolve um problema chamando a si mesma em instâncias menores do mesmo problema.
  • Dois ingredientes essenciais:
    1. Base(s) da recursão: casos simples que se resolvem sem chamada recursiva.
    2. Passo recursivo: reduz o problema a uma instância menor e delega a resolução à própria função.
  • No caso da busca sequencial, é natural usar como estado corrente o índice i da posição que estamos testando. Cada chamada recursiva testa v[i] e, se não for, avança para i+1.
  • Portanto:
    • Base 1: se i = n significa que já percorremos todo o vetor sem achar x → retornar -1.
    • Base 2: se v[i] = x → retornar i.
    • Passo recursivo: se v[i] \neq x e i < n, chamar a função para i+1.

Passo 3

Construção do algoritmo recursivo (esqueleto e explicação de cada linha).
  • Vamos definir uma função auxiliar recursiva com assinatura
    \text{recursive\_search}(v, n, x, i),
    onde i é o índice atual a ser testado.
  • Casos e ações:
    1. Se i = n: não há mais elementos; retornar -1.
    2. Se v[i] = x: achamos; retornar i.
    3. Caso contrário: retornar a chamada recursiva \text{recursive\_search}(v, n, x, i+1).
  • Para esconder o parâmetro i do usuário, fornece-se uma função wrapper
    \text{search}(v, n, x) que chama \text{recursive\_search}(v, n, x, 0).

Passo 4

Pseudocódigo final da solução (linha a linha, explicando o que cada símbolo significa).
  • Significados:
    • v: vetor de entrada.
    • n: tamanho do vetor (número de posições, indice máximo é n-1).
    • x: elemento que queremos achar.
    • i: índice atual que estamos verificando.
    • Retorno -1 significa “não encontrado”.
  • Pseudocódigo:
    function \text{recursive\_search}(v, n, x, i)
    • if i = n then
      • return -1
    • if v[i] = x then
      • return i
    • return \text{recursive\_search}(v, n, x, i+1)
    function \text{search}(v, n, x)
    • return \text{recursive\_search}(v, n, x, 0)

Passo 5

Raciocínio por que isso funciona (intuição e prova por indução simples).
  • Intuição: cada chamada testa uma posição diferente do vetor; ou encontra x e retorna seu índice, ou avança até ultrapassar o último índice e retorna -1. Não há saltos nem omissões.
  • Prova por indução no número de elementos restantes (esboço simples):
    • Caso base: se restam 0 elementos (isto é, i = n), comprovamos que retornar -1 está correto porque não há mais posições a verificar.
    • Passo indutivo: suponha que para qualquer chamada com índice maior que i a função funciona. Na chamada com índice i, se v[i] = x retorna corretamente i; caso contrário, chama a função para i+1 que, por hipótese indutiva, retorna o índice correto se existe ou -1 caso não exista. Logo a chamada em i também está correta.
  • Conclusão: a função retorna o índice do primeiro encontro de x ou -1 se não estiver no vetor.

Passo 6

Complexidade e observações práticas (o que levar em conta na prova).
  • Complexidade de tempo: cada chamada testa exatamente uma posição; no pior caso percorre todas as n posições. Portanto tempo é O(n).
  • Complexidade de espaço: por causa das chamadas recursivas empilhadas, o custo de memória é O(n) no pior caso (profundidade máxima da recursão é n). Em linguagens que não otimizam recursão de cauda, isso pode estourar a pilha para n muito grande.
  • Observação prática: a versão recursiva é elegante e fácil de provar, mas a versão iterativa (loop) usa O(1) espaço extra e, em provas/concursos, costuma ser preferida por questões de eficiência. Ainda assim, a recursiva é didática para entender decomposição do problema.

Passo 7

Exemplo passo a passo para fixar (trace manual para aprender a aplicar durante a prova).
  • Suponha v = [3, 5, 2, 7], n = 4, x = 7.
  • Chamamos \text{search}(v, 4, 7) que faz \text{recursive\_search}(v,4,7,0).
    • Chamada \text{recursive\_search}(v,4,7,0):
      • i=0, v[0]=3 \neq 7 → chama com i=1.
    • Chamada \text{recursive\_search}(v,4,7,1):
      • i=1, v[1]=5 \neq 7 → chama com i=2.
    • Chamada \text{recursive\_search}(v,4,7,2):
      • i=2, v[2]=2 \neq 7 → chama com i=3.
    • Chamada \text{recursive\_search}(v,4,7,3):
      • i=3, v[3]=7 = x → retorna 3.
    • As chamadas anteriores recebem esse retorno e o propagam, então o resultado final é 3.
  • Se x fosse 4 (não presente), a sequência avançaria até i=4 e então retornaria -1.

Passo 8

Dicas para a prova (como escrever rápido e perder menos pontos).
  • Escreva primeiro a versão wrapper \text{search}(v,n,x) que chama a auxiliar com i=0. Isso evita confusão com parâmetros iniciais.
  • Declare claramente as bases: “se i=n retorna -1” e “se v[i]=x retorna i”.
  • Seja explícito que a chamada recursiva é com i+1.
  • Se pedirem análise de complexidade, mencione O(n) tempo e O(n) espaço (por pilha).
  • Se for solicitado, apresente também a versão iterativa e compare espaço usado.

Resposta

function \text{recursive\_search}(v, n, x, i)
  • if i = n then return -1
  • if v[i] = x then return i
  • return \text{recursive\_search}(v, n, x, i+1)
function \text{search}(v, n, x)
  • return \text{recursive\_search}(v, n, x, 0)

Exercícios relacionados