Pessoal, olhem a recursão abaixo, alguém poderia me explicar passo a passo o que ele faz?
Realmetne não consegui entender pq a saída é 116. Parece que ele só diminui de um lado na hora de chamar a função novamente e depois vai diminuir o outro lado.
Se alguém puder explicar agradeço.
public class teste {
public static void main(String args[]) {
System.out.println("teste");
teste test = new teste();
int t = test.algoritmo(6);
System.out.println("n vale: " + t);
}
public int algoritmo(int N) {
System.out.println("N vale: " + N);
if (N == 1 || N == 2) {
return N;
} else {
return algoritmo(N-1) + N * algoritmo(N-2);
}
}
}
Mas é isso mesmo que acontece.
A recursão é feita à esquerda primeiro. Quando a chamada recursiva à esquerda terminar (quando N for igual a 1 ou 2), ai sim começará a chamada à direita.
Faça um teste de mesa, dividindo cada passo da recursão.
Não adianta tentar “explicar” o que ele faz… só fazendo o teste de mesa mesmo… sabe fazer um teste de mesa? É bem simples, meio trabalhoso, mas simples… Daí você vai entender o resultado, apesar de eu não saber pra que serve esse algoritmo, alguém lembra o que é isso aí?
E você tem dúvidas quanto á recursividade, como ela funciona?
a) algoritmo (6) = algoritmo (5) + (...) // Não interessa o que vem depois porque tenho de calcular primeiro o algoritmo(5)
b) algoritmo (5) = algoritmo (4) + (...) // Da mesma forma não interessa o que vem depois
c) algoritmo (4) = algoritmo (3) + (...) // Sempre a mesma coisa
d) algoritmo (3) = algoritmo (2) + (...) // Sempre a mesma coisa
e) algoritmo (2) = 2 // Esse eu já sei o valor, pode voltar para d) e continuar
d) algoritmo (3) = 2 + 3 * algoritmo(1) // Agora tenho de saber o algoritmo de 1
f) algoritmo (1) = 1 //tem a reposta para o 1, continua d)
d) algoritmo(3) = 2 + 3 = 5 // tenho algoritmo(3), posso continuar c)
c) algoritmo (4) = 5 + 4 * algoritmo (2) // tenho de saber o algoritmo de 2 (é 'burro' e não sabe que já calculou)
g) algoritmo (2) = 2
(...) // and so on and so on
Eu não entendi o seguinte, ele começa no 6 e da um return(N - 1) e N então vale 5, depois 4, 3, e quando chega no 2 ele dá um return na função então ele não acessa o 1. Portanto, tem-se o 6,5,4,3,2 empilhados. Agora ele vai para o algoritmo(N - 2) mas qual o valor de N? Ele guardou o 6 de antes pra fazer a mesma coisa que fez no algoritmo(N-1) anterior? e quando ele faz a soma e a multiplicação?
Me desculpem mas eu já tinha lido o outro tópico e não entendi, e novamente não consegui entender essa recursão.
Acho que é isso ai mesmo. olha F(6) = F(5) + 6F(4) ou seja se F(5) = F(4) + 5F(3) Dai o F(4) =F(3) + 4F(2) e F(3)= F(2) + 3F(1) dai quando chega função de F(2) E F(1) fica irredutivel.
edit: meu fluxo tava errado crtl +c ctrl+v da sempre errado +) da uma olhada ai que você vai conseguir tenho certeza
faz no papel msm cara.
[quote=regissl]Eu não entendi o seguinte, ele começa no 6 e da um return(N - 1) e N então vale 5, depois 4, 3, e quando chega no 2 ele dá um return na função então ele não acessa o 1. Portanto, tem-se o 6,5,4,3,2 empilhados. Agora ele vai para o algoritmo(N - 2) mas qual o valor de N? Ele guardou o 6 de antes pra fazer a mesma coisa que fez no algoritmo(N-1) anterior? e quando ele faz a soma e a multiplicação?
Me desculpem mas eu já tinha lido o outro tópico e não entendi, e novamente não consegui entender essa recursão.
Se alguém puder detalhar melhor eu agradeço.
Obrigado de qualquer forma.
Att,
Regis[/quote]
Só com teste de mesa… não tem outra solução, explicação, magia, ou qualquer outro tipo de coisa que vá te ajudar á entender melhor do que um teste de mesa… abre uma planilha do Excel, faça as colunas pra ir marcando os valores, e pra cada passo faça uma linha nova com os valores, só assim você vai entender…
O que eu não estou entendendo é o fluxo.
Primeiro ele chama o return algoritmo(N-1) até encontrar o 2, depois o N volta a ser 6 (como?) e chama N * algoritmo(N-2) passando N-2 ou seja 4, depois 2 e cai fora porque eh 2.
No fim do processo temos 5 + 6 * 4, 4 + 5 * 2…
Já calculei e não da certo, enfim o fluxo dele está estranho pra mim.
guialeixo agora entendi o seu raciocínio. No entanto, ainda continuo sem entender o fluxo. O que é empilhado primeiro, quem afinal dos dois esta chamando a função, os dois ao mesmo tempo?
Esse fluxo não to conseguindo entender.
Agora entendo porque minha professora dizia que recursão era uma questão de fé
[quote=regissl]guialeixo agora entendi o seu raciocínio. No entanto, ainda continuo sem entender o fluxo. O que é empilhado primeiro, quem afinal dos dois esta chamando a função, os dois ao mesmo tempo?
Esse fluxo não to conseguindo entender.
Agora entendo porque minha professora dizia que recursão era uma questão de fé
Obrigado.
Att,
Regis[/quote]
Cara num é questão de fé nao. é questao de logica você so precisa parar de pensar no codigo e pegar a logica do negocio, pensa o seguinte se é n = 6 logo a F(6) = F(6-1) 6 * (F6-2) => F(5) 6*(F4) => F(F(5-1) 5 * F(5-2)) 6 * F(F(4-1) 4*F(4-2)) => … agora continue
[quote=regissl]guialeixo agora entendi o seu raciocínio. No entanto, ainda continuo sem entender o fluxo. O que é empilhado primeiro, quem afinal dos dois esta chamando a função, os dois ao mesmo tempo?
Esse fluxo não to conseguindo entender.
Agora entendo porque minha professora dizia que recursão era uma questão de fé
Obrigado.
Att,
Regis[/quote]
Então sua professora deveria tomar vergonha na cara dela. Falar que é questão de fé é pq nem ela entende.
Uma forma fácil de entender a recursão seria vc construir (na mão mesmo) uma árvore.
Veja a execução do método recursivo para o valor 6 que você deu o exemplo. Note que usei “alg” como nome da função.
Tem duas imagens em anexo. A primeira é a árvore, a segunda é o caminho que é executado.
Note que o caminho executado pela sua funlçao é um caminho “em ordem”.
Entenda bem isso ai, é bom pra você entender o conceito de pilha… já ouviu falar num erro chamado stackOverflow? Pega esse exemplo, e tenta entender porque ele acontece… ou poderia acontecer nesse caso da recursão…
