Escrever uma função recursiva int procuraLinear(int
, int
, int
) que retorna o índice da posição em que o valor
aparece no vetor
(de
elementos). Caso o valor
não esteja presente em
, a função deve retornar -1.
Passo 1
O enunciado pede uma função recursiva em C chamada procuraLinear que, dado um vetor v de n elementos e um valor k, retorna o índice da primeira ocorrência de k em v ou -1 se k não estiver no vetor. O conteúdo da matéria é recursão aplicada à busca linear em vetores.
Passo 2
Definimos o caso base da recursão: se n for igual a 0, significa que já percorremos todo o vetor sem encontrar k, logo retornamos -1.
Passo 3
No passo recursivo, com n>0, comparamos o primeiro elemento v[0] com k. Se forem iguais, retornamos 0, pois encontramos k na posição inicial do trecho atual do vetor.
Passo 4
Se v[0] não for igual a k, chamamos procuraLinear sobre o subvetor v+1 (ignorando o primeiro elemento) com tamanho n-1. Se a chamada recursiva retornar -1, propagamos esse -1. Caso contrário, adicionamos 1 ao resultado para ajustar o índice em relação ao vetor original.
Resposta
int procuraLinear(int v[], int n, int k) {
// Caso base: vetor vazio, não encontrou k
if (n == 0) {
return -1;
}
// Se o primeiro elemento for k, retorna índice 0
if (v[0] == k) {
return 0;
}
// Busca recursiva no restante do vetor
int res = procuraLinear(v + 1, n - 1, k);
if (res == -1) {
return -1; // não encontrou em v+1 … v[n-1]
}
// ajusta o índice para o vetor original
return res + 1;
}
// Caso base: vetor vazio, não encontrou k
if (n == 0) {
return -1;
}
// Se o primeiro elemento for k, retorna índice 0
if (v[0] == k) {
return 0;
}
// Busca recursiva no restante do vetor
int res = procuraLinear(v + 1, n - 1, k);
if (res == -1) {
return -1; // não encontrou em v+1 … v[n-1]
}
// ajusta o índice para o vetor original
return res + 1;
}