Higher value of a vector, with recursion

Asked

Viewed 4,641 times

2

I’m studying recursion and vectors, but I can’t understand how this method works, which returns the highest value using recursion.

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;
}
c array recursion
  • 1

    Do a "table test" with, say, n = 5, and you’ll understand (and will even validate if the implementation is correct).

  • 1

    To understand it would also be good to add a printf in the x values in this method. So you will understand the flux triggered in each recursion call.

  • The tip of José X is good, it is better with the tip of Giuliana Bezerra because it allows to see the table test during the execution, obviously it is good to take a break in each iteration, or even in each print to view the data and analyze calmly and gets closer than it would in a table test.

  • Hmm, I get it..

1 answer

3


First, this function would be called something like this:

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

Recursively, except when the n is 1, it will always fall on else, creating a recursive call sequence like this (this is the process of going):

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

At this point, the if will no longer fall into the else and return the element v[0]. Then at each iteration will start the process of turning back, where it will take the value of the previous iteration and compare with the n-nth position of the array, always choosing the largest and returning the largest to the top call.

With that, here’s what happens:

  • In the deepest iteration (the last) it only returns the first value.
  • In the second deepest iteration (the penultimate), it compares the second value with the one obtained from the last iteration.
  • In the third deepest iteration (the antepenultimate), he compares the third value with that obtained from the penultimate iteration.
  • ...
  • In the first iteration (the shallowest), it compares the last value with the one obtained from the second iteration.

Therefore, in the end the chosen value will be the largest element.

Browser other questions tagged c array recursion

You are not signed in. Login or sign up in order to post.