2

Eu estou estudando sobre recursão e vetores, mas não consigo entender como funciona esse método, que retorna o maior valor usando recursão.

int maximoR (int n, int v[]) {
   int x;
   if (n == 1) x = v[0];
   else {
      x = maximoR (n-1, v); 
      if (x < v[n-1]) x = v[n-1];
   }
   return x;
}
4
  • 1
    Faça um "teste de mesa" com, digamos, n = 5, e você vai entender (e vai inclusive validar se a implementação está correta).
    – zentrunix
    5/09/2016 às 15:02
  • 1
    Pra entender também seria bom adicionar uns printf nos valores de x nesse método. Assim você vai entender o fluxo desencadeado em cada chamada da recursão. 5/09/2016 às 15:03
  • A dica do José X é boa, fica melhor com a dica da Giuliana Bezerra porque permite ver o teste de mesa durante a execução, obviamente que é bom dar uma pausa em cada iteração, ou mesmo em cada impressão para ver os dados e analisar com calma e fica mais próximo do que faria em um teste de mesa.
    – Maniero
    5/09/2016 às 15:05
  • Humm, entendi..
    – user54858
    5/09/2016 às 15:09

1 Resposta 1

3

Primeiramente, essa função seria chamada mais ou menos assim:

int valores[] = {5, 10, 4, -4, 2, -7, 9};
int max = maximoR(7, valores); /* 7 = tamanho do vetor. */

Recursivamente, exceto quando o n é 1, ele sempre cairá no else, criando uma sequência de chamadas recursivas assim (esse é o processo de ida):

maximoR(6, v);
maximoR(5, v);
maximoR(4, v);
maximoR(3, v);
maximoR(2, v);
maximoR(1, v);

Neste ponto, o if não cairá mais no else e retornará o elemento v[0]. Em seguida, a cada iteração vai iniciar o processo de volta, onde pegará o valor da iteração anterior e vai comparar com o da n-ésima posição do array, sempre escolhendo o maior e retornando esse maior para a chamada superior.

Com isso, eis o que ocorre:

  • Na iteração mais profunda (a última) ele apenas retorna o primeiro valor.
  • Na segunda iteração mais profunda (a penúltima), ele compara o segundo valor com o obtido da última iteração.
  • Na terceira iteração mais profunda (a antepenúltima), ele compara o terceiro valor com o obtido da penúltima iteração.
  • ...
  • Na primeira iteração (a mais rasa), ele compara o último valor com o obtido da segunda iteração.

Assim sendo, no final o valor escolhido será o maior elemento.

0

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 .