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:
- Se o vetor só tiver 1 elemento, então esse elemento é o máximo
- Pegue o máximo do vetor excluindo a última posição
- 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 python como uma sugestão de exercício ao leitor: escrever esses trechos de código em c ou c++. 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:
- seu difrecursivo é uma função pura
- fácil de verificar pois não há efeitos colaterais
- o resultado da sua chamada é sobrescrito logo em seguida
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.