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
de tamanho
e um elemento
a ser buscado, o algoritmo percorre as posições
comparando
com
. Se encontrar
, retorna o índice
onde foi encontrado; caso contrário, retorna um valor indicando que
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
de tamanho . - Há um elemento alvo
que queremos encontrar no vetor. - O algoritmo deve percorrer as posições
comparando com . - Se encontrar
, deve retornar o índice onde foi encontrado; caso contrário, retornar um valor indicando “não encontrado” (por exemplo ). - 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:
- Base(s) da recursão: casos simples que se resolvem sem chamada recursiva.
- 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
da posição que estamos testando. Cada chamada recursiva testa e, se não for, avança para . - Portanto:
- Base 1: se
significa que já percorremos todo o vetor sem achar → retornar . - Base 2: se
→ retornar . - Passo recursivo: se
e , chamar a função para .
- Base 1: se
Passo 3
Construção do algoritmo recursivo (esqueleto e explicação de cada linha).
- Vamos definir uma função auxiliar recursiva com assinatura
,
ondeé o índice atual a ser testado. - Casos e ações:
- Se
: não há mais elementos; retornar . - Se
: achamos; retornar . - Caso contrário: retornar a chamada recursiva
.
- Se
- Para esconder o parâmetro
do usuário, fornece-se uma função wrapper
que chama .
Passo 4
Pseudocódigo final da solução (linha a linha, explicando o que cada símbolo significa).
-
Significados:
-
: vetor de entrada. -
: tamanho do vetor (número de posições, indice máximo é ). -
: elemento que queremos achar. -
: índice atual que estamos verificando. - Retorno
significa “não encontrado”.
-
-
Pseudocódigo:
function- if
then - return
- return
- if
then - return
- return
- return
function- return
- if
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
e retorna seu índice, ou avança até ultrapassar o último índice e retorna . Não há saltos nem omissões. - Prova por indução no número de elementos restantes (esboço simples):
- Caso base: se restam
elementos (isto é, ), comprovamos que retornar está correto porque não há mais posições a verificar. - Passo indutivo: suponha que para qualquer chamada com índice maior que
a função funciona. Na chamada com índice , se retorna corretamente ; caso contrário, chama a função para que, por hipótese indutiva, retorna o índice correto se existe ou caso não exista. Logo a chamada em também está correta.
- Caso base: se restam
- Conclusão: a função retorna o índice do primeiro encontro de
ou 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
posições. Portanto tempo é . - Complexidade de espaço: por causa das chamadas recursivas empilhadas, o custo de memória é
no pior caso (profundidade máxima da recursão é ). Em linguagens que não otimizam recursão de cauda, isso pode estourar a pilha para muito grande. - Observação prática: a versão recursiva é elegante e fácil de provar, mas a versão iterativa (loop) usa
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
, , . - Chamamos
que faz . - Chamada
: -
, → chama com .
-
- Chamada
: -
, → chama com .
-
- Chamada
: -
, → chama com .
-
- Chamada
: -
, → retorna .
-
- As chamadas anteriores recebem esse retorno e o propagam, então o resultado final é
.
- Chamada
- Se
fosse (não presente), a sequência avançaria até e então retornaria .
Passo 8
Dicas para a prova (como escrever rápido e perder menos pontos).
- Escreva primeiro a versão wrapper
que chama a auxiliar com . Isso evita confusão com parâmetros iniciais. - Declare claramente as bases: “se
retorna ” e “se retorna ”. - Seja explícito que a chamada recursiva é com
. - Se pedirem análise de complexidade, mencione
tempo e espaço (por pilha). - Se for solicitado, apresente também a versão iterativa e compare espaço usado.
Resposta
function
- if
then return - if
then return - return
function
- return