-2

Boa tarde! Tô muito perdida nessa questão de um trabalho da faculdade porque acabei não entendendo recursividade direito. Alguém poderia me ajudar?
Eu preciso disso aqui: Uma função que retorne o índice na qual o elemento buscado for encontrado ou -1 caso o elemento não esteja presente. Ela recebe, como argumento, o vetor de inteiros, o início e o fim do intervalo analisado a cada recursão, além do valor a ser buscado.
O meu código tá assim até agora (basicamente tirei da internet pq não soube onde começar)

#include <stdio.h>
#define TAMANHO 6

int bin_search (int *v, int begin, int end, int value){
    int i = (begin + end)/2; //meio do vetor


    if (begin > end){
        return -1; //se o inicio for maior que o fim > -1 (não é decrescente)
    }
    if (v[i] == value){  //vetor do meio = valor?
        return i;
    }
    if(v[i] < value){ //se o valor for maior que o vetor do meio = fim do vetor
        return bin_search(v, i+1,end,value);
    }
    else if (v[i] > value) { //se o valor de i for maior que valor = inicio do vetor.
        return bin_search(v, begin, i-1,value);
    }
}

int main (){
    int v [TAMANHO] = {1, 3, 5, 10, 20, 30};
    int i,begin,end;

    for(i = 0; i < TAMANHO; i++){
        int value = v[i];            

        printf("Busca binaria recursiva: %d\n",value,bin_search(v,0,TAMANHO -1, value));    
    }    
}

Como eu retorno o início e o fim? A entrada de dados também tá um pouco complicada pra mim.
Obrigada desde ja <3

1 Resposta 1

1

Para entender recursão utilizemos um laço de repetição para alcançar o mesmo objetivo.

#include <stdio.h>
#define TAMANHO 6

int search (int *v, int begin, int end, int value) {
    int i = begin;
    for (i = begin; i < end; i++) {
        if(v[i] == value) return i;
    }
    return -1;
}

int main() {
    int v [TAMANHO] = {1, 3, 5, 10, 20, 30};
    int i;

    for(i = 0; i < TAMANHO; i++) {
        int value = v[i];            

        printf("Busca linear encontrou %d em v[%d]\n", value, search(v, 0, TAMANHO, value));
    }
    return 0;
}

O algoritmo verifica cada número e retorna o índice daquele número ou -1 se já checou todos. Reimplementar esse algoritmo de maneira recursiva é uma questão de identificar os casos base if(v[i] == value) return i; e if(!(i < end)) return -1, o último passo do for, e identificar o passo seguinte que é continuar a procurar na lista com outro índice.

#include <stdio.h>
#define TAMANHO 6

int search (int *v, int begin, int end, int value) {
   int i = begin;
   // Retorne -1 caso não encontremos em toda a lista
   if (begin > end) {
       return -1; 
   }
   // Retorne o índice caso encontremos o valor 
   if (v[i] == value) { 
       return i;
   }
   // Continue a procura
   return search(v, i + 1, end, value);
}

int main () {
   int v [TAMANHO] = {1, 3, 5, 10, 20, 30};
   int i;

   for(i = 0; i < TAMANHO; i++) {
       int value = v[i];            

       printf("Busca recursiva encontrou %d em v[%d]\n", value, search(v, 0, TAMANHO, value));
   }
   printf("Busca recursiva de %d retornou %d\n", 2, search(v, 0, TAMANHO, 2));
   return 0;
}

Como a descrição do problema que você tem não garante a ordenação crescente dos itens na lista, eu não tenho como implementar a função usando o algoritmo de busca binária, que não deve ser difícil de encontrar pela internet.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .