The difference between the value of a maximum and minimum element of a vector recursively

Question

I made that code :

int difrecursivo(int *vetor,int tam){
   if(tam == 1)
        return vetor[0];
    else{
        int max = vetor[0];
        if(max < vetor[tam-1])
            max = vetor[tam-1];
        int min = vetor[0];
        if(min > vetor[tam-1])
            min = vetor[tam-1];
        int total = difrecursivo(vetor, tam-1);
        total = max-min;
        if(total < 0)
            return -(total);
        return total;
    }
}

With this code I can even get the difference between the largest and smallest element of a vector, but only when the size of this vector is up to 5, above this value the code does not work as it should.
I have to use recursiveness in this function.
Help me solve so that it always takes the difference between the maximum and minimum value of a size independent vector.

Answer 1

A lot depends on how the solution strategy will be. This will define the path recursive to be traversed. For example, take the following recursive algorithm to calculate the maximum:

1. If the vector has only 1 element, then that element is the maximum
2. Take the maximum vector excluding the last position
3. Compare this maximum with the last element of the vector and return the largest

I will use an auxiliary function that returns me the maximum between two integers, just for the record:

int _max(int a, int b) {
    return a >= b? a: b;
}

So I can easily define the recursive function this way:

int max_recursiv_1(int *v, int tam) {
    if (tam == 1) {
        return v[0];
    } else {
        return _max(max_recursiv_1(v, tam - 1), v[tam - 1]);
    }
}

The strategy used here is:

• reduce to a minor problem
• solve the minor problem
• check the differential of the original problem and the smallest, computed with the answer to the minor problem

However, this is not the only strategy that can be used. There are others as well, with very interesting potential. For example:

• check the differential of the original and minor problem, getting answer partial
• Enter with previously known partial response
• pass the partial answer to the minor problem
• the answer of the minor problem + partial answer is the answer of the problem original

How would I find the ultimate in this strategy? To do so, I need to increase the number of parameters, then including the partial response parameter:

int max_recursiv_2(int *v, int tam, int max_parcial) {
    if (tam == 0) {
        return max_parcial;
    } else {
        return max_recursiv_2(v, tam - 1, _max(v[tam - 1], max_parcial));
    }
}

Notice how now computation is done at every step, not being necessary recursive function return post-processing? There is also another recursive function change behavior: there is no need to worry about the minimum case (in this case, the minimum case was when there was only one element in the vector), but rather detection of "empty problem".

What is an empty problem? Well, find the maximum in a list of 0 elements. This problem is empty, does not admit valid answer other than null or another vacuous indicator. This means that the partial response obtained in this end of the appeal is the final.

Another change that occurs is: and how do I call the recursive function? I need to know how to get a partial answer before calling it? This does not would be a standardizable routine?

The answer is that yes, is standardizable. For example, a partial response to maximum is any element in the list. In this case, we can take advantage of the answer partial and reduce the problem:

int max_recursiv_entrada(int *v, int tam) {
    return max_recursiv_2(v, tam - 1, v[tam - 1]);
}

In the example, we take the last element of the vector as a partial response and, also, remove it from the processing list.

And why did I bring it up? Well, if we had a function that comes back, some way, minimum and maximum? How I would do a processing only after return of the recursive function?

I can start with a base case: if it only has 1 element, it is the minimum and the maximum. Something like that:

def min_max_recur_1(vetor, tam):
  if tam == 1:
    return (vetor[0], vetor[0])
  # ...

The codes shown are in python as a suggestion to exercise reader: write these snippets of code on c or c++. Of other languages that would also open the possibility of this exercise, the facility reading and expression were also decisive reasons for the choice python.

And how would I make the recursive step? Well, I should assemble another response tuple comparing with the item in question:

def min_max_recur_1(vetor, tam):
  if tam == 1:
    return (vetor[0], vetor[0])
  else:
    resp_menor = min_max_recur_1(vetor, tam - 1)
    return (min(resp_menor[0], vetor[tam - 1]), max(resp_menor[1], vetor[tam - 1]))

See running on ideone

Okay, that worked well. But, what if it was interesting for me to use the strategy of passing the partial response to the next steps of recursion? I can build the answer to every step and pass it down. Again, it is necessary to have a first step which is the creation of the first response partial, which is one of the elements being the maximum and at the very least:

def min_max_entrada(vetor, tam):
  return min_max_recur_2(vetor, tam - 1, vetor[tam - 1], vetor[tam - 1])

def min_max_recur_2(vetor, tam, min_parcial, max_parcial):
  if tam == 0:
    return (min_parcial, max_parcial)
  else:
    return min_max_recur_2(vetor, tam - 1, min(min_parcial, vetor[tam - 1]), max(max_parcial, vetor[tam - 1]))

See running on ideone

Everything quiet so far. We managed in a single recursion to find the maximum and the minimum of a list. However, we do not want these results by themselves, but rather a computation on them. What computation? The difference between the minimum and the maximum. Recursion is concerned, now, to seek this difference, while on the output global I wish to apply this specific function. As in the last step I already I have the result of the recursion, just then, instead of returning the answer required by the recursive step, the specific function on that recursion:

def dif_min_max_entrada(vetor, tam):
  if tam <= 1:
    return 0
  else:
    return dif_min_max_recur(vetor, tam - 1, vetor[tam - 1], vetor[tam - 1])

def dif_min_max_recur(vetor, tam, min_parcial, max_parcial):
  if tam == 0:
    return max_parcial - min_parcial
  else:
    return dif_min_max_recur(vetor, tam - 1, min(min_parcial, vetor[tam - 1]), max(max_parcial, vetor[tam - 1]))

See running on ideone

The fact that we use partial recursion responses implies that we don’t need We worry about some return post-processing. In more direct strategy recursion, where the minor case is solved and then the answer is computed with the case differential, the recursion response is obtained at each step and needs to be processed, so any processing done about the response final must necessarily be external to recursion.

There is some care that I took and took in that response. The first is that necessarily the difference between the minimum and the maximum, when there is only 1 only element, is 0, because this element will be at the same time the minimum and the maximum. The second care I took is that, necessarily, the maximum will be not less than the minimum. Then the difference between the two will always be a no number negative, so it is not necessary to check for nullity.

In contrast to her answer, she does not give the right answer even to vectors of 5 elements. Take the following case: {3, 5, 1, 2}. What is the answer expected? 4, that is 5 - 1. What answer will your algorithm provide? 1, which is the difference between the first and the last element.

His strategy was to try to find, in the recursive function, the difference between minimum and maximum and then use the original problem differential to try to increase the response of the minor problem. Only this strategy is condemned, because recursion fails to produce the answer you need.

Let’s take that, in the recursive call, we get the result 4, and for some reason this is the correct answer to the minor case. So we have to difference between the smallest case and the original case is the number 7. What’s the big deal expected given this?

In reality, it is not possible to know, precisely because the answer obtained by recursion cannot inform sufficiently to obtain the difference between the minimum and maximum. Which answers could result in the difference 4 among the extreme values? We could have 1007 and 1003, so the new difference should be 1000. Just like, if it was 10 and 6, the answer should continue as 4. Therefore, this paragraph and the previous one demonstrate that it is useless any attempt to resolve the recursion, with the recursion response being difference between minimum and maximum, using this strategy.

Now, going back to his code, how will he behave for the entrance {3, 5, 1, 2}? Note that it has size 4. As I commented on the question, in practice the recursive call is ignored from the processing. And I know this due to 2 factors:

• your difrecursivo is a pure function
  • easy to check because there is no side effects
• the result of your call is overwritten right after

So if you removed the pieces of code with wasted processing, it gets like this:

int difrecursivo(int *vetor,int tam){
   if(tam == 1)
        return vetor[0];
    else{
        int max = vetor[0];
        if(max < vetor[tam-1])
            max = vetor[tam-1];
        int min = vetor[0];
        if(min > vetor[tam-1])
            min = vetor[tam-1];
        int total; // REMOVIDO = difrecursivo(vetor, tam-1);
        total = max-min;
        if(total < 0)
            return -(total);
        return total;
    }
}

Another also Detahe that we can remove is the second if. The construction of min and max ensure that min <= max, soon total >= 0. Clearing the code even further:

int difrecursivo(int *vetor,int tam){
   if(tam == 1)
        return vetor[0];
    else{
        int max = vetor[0];
        if(max < vetor[tam-1])
            max = vetor[tam-1];
        int min = vetor[0];
        if(min > vetor[tam-1])
            min = vetor[tam-1];
        int total;
        total = max-min;
        return total;
    }
}

Removing unnecessary variables and sort the code a bit:

int difrecursivo(int *vetor,int tam){
   if(tam == 1)
        return vetor[0];
    else{
        int max, min;
        min = max = vetor[0];

        if(max < vetor[tam-1])
            max = vetor[tam-1];
        if(min > vetor[tam-1])
            min = vetor[tam-1];

        return max-min;
    }
}

Thus, it is easy to realize that there are only 2 possible values for min and for max: or is vetor[0] or is vetor[tam - 1]. The result would be equivalent to the following code (for _min and _max that I defined formerly):

int difrecursivo(int *vetor,int tam){
   if(tam == 1)
        return vetor[0];
    else
        return _max(vetor[0], vetor[tam - 1]) - _min(vetor[0], vetor[tam - 1]);
}

So, trivially I talk that answer to the input {3, 5, 1, 2} is 1.

The only option I know that could solve your problem using recursion head would have a recursive function to determine the maximum and minimum of the list and another function, separate, that takes this value and takes away the difference. Thing similar to the tail recursion I proposed, only in it the function non-recursive cares about treating the input to perform the recursive function, whereas in this case there would be a preparation of the output of the recursive function to something useful.