-2

Fiz esse código :

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;
    }
}

Com esse código eu até consegue tirar a diferença entre o maior e o menor elemento de um vetor, mas só quando o tamanho deste vetor é até 5, acima desse valor o código não funciona como deveria.
Tenho que usar recursividade nessa função.
Me ajudem a resolver de modo que sempre tire a diferença entre o valor máximo e minimo de um vetor independente do tamanho.

1
  • 1
    Qual a entrada que dá errado? Já tentou fazer um teste de mesa com essa entrada? E por que você inicia o valor de total com o resultado da função para logo em seguida sobrescrever esse valor com a diferença, jogando a recursão toda no lixo? 27/08/2019 às 17:25

1 Resposta 1

2

Muito depende de como será a estratégia de solução. Isso definirá o caminho recursivo a ser percorrido. Por exemplo, pegue o seguinte algoritmo recursivo para se calcular o máximo:

  1. Se o vetor só tiver 1 elemento, então esse elemento é o máximo
  2. Pegue o máximo do vetor excluindo a última posição
  3. Compare esse máximo com o último elemento do vetor e retorne o maior

Vou usar de uma função auxiliar que me retorne o máximo entre dois inteiros, só para constar:

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

Então posso facilmente definir a função recursiva desse jeito:

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]);
    }
}

A estratégia usada aqui é:

  • reduza para um problema menor
  • resolva o problema menor
  • verifique o diferencial do problema original e o menor, computano com a resposta do problema menor

Porém, essa não é a única estratégia possível de ser usada. Tem outras também, com potencial bem interessante. Por exemplo:

  • verifique o diferencial do problema original e do menor, obtendo resposta parcial
  • compute com a resposta parcial previamente conhecida
  • passe a resposta parcial para o problema menor
  • a resposta do problema menor + resposta parcial é a resposta do problema original

Como seria achar o máximo nessa estratégia? Para tal, eu preciso aumentar o número de parâmetros, incluindo então o parâmetro com a resposta parcial:

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));
    }
}

Notou como agora a computação é feita a cada passo, não sendo necessário pós-processamento do retorno da função recursiva? Também tem outra mudança de comportamento: não é necessário se preocupar com o caso mínimo (no caso, o caso mínimo era quando só havia um elemento no vetor), mas sim detecção de "problema vazio".

O que é um problema vazio? Bem, achar o máximo em uma lista de 0 elementos. Esse problema é vazio, não admite resposta válida a não ser null ou outro indicador de vacuosidade. Isso significa que a resposta parcial obtida nesse fim da recursão é a repsosta definitiva.

Outra mudança que ocorre é: e como eu faço a chamada da função recursiva? Eu preciso conhecer como obter uma resposta parcial antes de chamá-la? Isso não seria uma rotina padronizável?

A resposta é que sim, é padronizável. Por exemplo, uma resposta parcial para o máximo é qualquer elemento da lista. No caso, podemos aproveitar a resposta parcial e reduzir o problema:

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

No exemplo, pegamos o último elemento do vetor como resposta parcial e, também, removemo-lo da lista de processamento.

E por que falei disso tudo? Bem, se tivéssemos uma função que retorne, de algum jeito, o mínimo e o máximo? Como eu faria um processamento só depois do retorno da função recursiva?

Posso começar através de um caso base: se só tem 1 elemento, ele é o mínimo e o máximo. Algo assim:

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

Os códigos mostrados estão em como uma sugestão de exercício ao leitor: escrever esses trechos de código em ou . De outras linguagens que também abririam a possibilidade desse exercício, a facilidade de leitura e de expressão também foram motivos decisivos para a escolha de Python.

E como eu faria o passo recursivo? Bem, deveria montar outra tupla de resposta comparando com o elemento em questão:

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]))

Veja sendo executado no ideone

Ok, assim funcionou bem. Mas, e se fosse interessante para mim usar a estratégia de passar a resposta parcial para os próximos passos da recursão? Eu posso construir a resposta a cada passo e passá-la para baixo. De novo, faz-se necessário ter um primeiro passo que é o de criação da primeira resposta parcial, que é um dos elementos ser o máximo e o mínimo:

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]))

Veja sendo executado no ideone

Tudo tranquilo até aqui. Conseguimos em uma única recursão achar o máximo e o mínimo de uma lista. Porém, não queremos esses resultados por si, mas sim uma computação sobre eles. Que computação? A diferença entre o mínimo e o máximo. A recursão se preocupa, agora, em buscar essa diferença, enquanto que na saída global eu desejo aplicar essa função específica. Como no último passo eu já tenho o resultado da recursão, basta então, no lugar de retornar a resposta exigida pelo passo recursivo, a função específica sobre essa recursão:

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]))

Veja sendo executado no ideone

O fato de usarmos as respostas parciais da recursão implica que não precisamos nos preocupar com algum pós-processamento do retorno. Na estratégia mais direta da recursão, em que se resolve o caso menor e depois se computa essa resposta com o diferencial dos casos, a resposta da recursão é obtida a cada passo e precisa ser processada, então qualquer processamento feito sobre a resposta final precisa, necessariamente, ser externo a recursão.

Tem alguns cuidados que aproveitei e tomei nessa resposta. O primeiro é que necessariamente a diferença entre o mínimo e o máximo, quando se tem apenas 1 único elemento, é 0, pois esse elemento sera, ao mesmo tempo, o mínimo e o máximo. O segundo cuidado que eu tomei é que, necessariamente, o máximo será não menor que o mínimo. Então a diferença entre ambos sempre será um número não negativo, logo não é necessário checar pela nulidade.

Em contraponto à sua resposta, ela não dá a resposta certa nem mesmo para vetores de 5 elementos. Pegue o seguinte caso: {3, 5, 1, 2}. Qual a resposta esperada? 4, que é 5 - 1. Qual resposta seu algoritmo vai fornecer? 1, que é a diferença entre o primeiro e o último elemento.

A sua estratégia foi de tentar encontrar, na função recursiva, a diferença entre o mínimo e o máximo e então usar o diferencial do problema original para tentar incrementar a resposta do problema menor. Só que essa estratégia está condenada, porque a recursão não consegue produzir a resposta que você precisa.

Vamos pegar que, na chamada recursiva, obtemos o resultado 4, e por algum motivo essa é a resposta correta para o caso menor. Então, temos que a diferença entre o caso menor e o caso original é o número 7. Qual a repsosta esperada dado isso?

Na real, não dá para saber, justamente porque a resposta obtida pela recursão não consegue informar o suficiente para, com isso, obter a diferença entre o mínimo e o máximo. Quais respostas poderiam resultar na diferença 4 entre os valores extremos? Poderíamos ter 1007 e 1003, portanto a diferença nova deveria ser 1000. Assim como, se fosse 10 e 6, a resposta deveria continuar como 4. Logo, esse parágrafo e o anterior demonstram que é inútil qualquer tentativa de resolver a recursão, com a resposta da recursão sendo a diferença entre o mínimo e o máximo, usando essa estratégia.

Agora, voltando ao seu código, como ele irá se comportar para a entrada {3, 5, 1, 2}? Note que ela tem tamanho 4. Conforme eu comentei na questão, na prática a chamada recursiva é ignorada do processamento. E eu sei disso devido a 2 fatores:

Então, se removidos os trechos de código com processamento desperdiçado, ele fica assim:

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;
    }
}

Outro detahe também que podemos remover é o segundo if. A construção de min e max garantem que min <= max, logo total >= 0. Limpando ainda mais o código:

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;
    }
}

Removendo variáveis desnecessárias e ordenando um pouco o código:

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;
    }
}

Assim, fica fácil perceber que só existem 2 valores possíveis para min e para max: ou é vetor[0] ou é vetor[tam - 1]. O resultado seria equivalente ao seguinte código (para os _min e _max que defini anteriormente):

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]);
}

Logo, trivialmente eu falo que a resposta para a entrada {3, 5, 1, 2} é 1.

A única opção que conheço que poderia resolver seu problema usando recursão de cabeça seria ter uma função recursiva para determinar o máximo e o mínimo da lista e outra função, separada, que pega esse valor e tira a diferença. Coisa semelhante ao da recursão de cauda que eu propus, só que nela a função não-recursiva se preocupa em tratar a entrada para executar a função recursiva, enquanto que nesse caso haveria um prepara da saída da função recursiva para algo útil.

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 .