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
- 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.
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?