Arquivo Discussoes de Programacao e Tecnologia Pessoal tem como me ajudarem a entender essa maldita recursao ja debuguei fiz tudo mas nao consigo entender pq pra mim o retorno seria 2 :(
public static void main(String[] args) {
int n = ff(7);
System.out.println(n);
}
public static int ff(int n){
//System.out.println(n);
if(n == 1){
return 1;
}
if((n % 2) == 0){
return ff(n/2);
}
return ff((n - 1)/2) + ff((n+1)/2);
}
Até onde eu consigo entender, pra ver se alguem consegue me ajudar:
ff(7) retorna ff(3)
ff(3) retorna ff(1)
ff(1) retorna 1. Então acaba a primeira recursao
depois nao consigo entender o que ocorre na segunda 
Então vamos por partes:
Começa com 7.
Como 7 é impar vai retornar ff(3) + ff(4)
Pegando no 3
Como 3 é impar vai retornar ff(1) + ff(2)
Pegando no 1
Pelo if, retorna 1
Pegando no 2
É par, retorna ff(1)
Pegando no 1
Pelo if, retorna 1
Temos então que ff(3) igual 1 + 1 = 2
Voltando acima ff(7) = 2 + ff(4)
Pegando no 4
É par, retorna ff(2)
Pegando no 2
É par, retorna ff(1)
Pegando no 1
Pelo if, retorna 1
Então, ff(4) = 1
Voltando acima, ff(7) = 2 + 1 = 3
O retorno é então 3 e não 2.
Então vamos por partes:
Começa com 7.
Como 7 é impar vai retornar ff(3) + ff(4)
Pegando no 3
Como 3 é impar vai retornar ff(1) + ff(2)
Pegando no 1
Pelo if, retorna 1
Pegando no 2
É par, retorna ff(1)
Pegando no 1
Pelo if, retorna 1
se ff(1) retorna 1 e ff(2) retorna ff(1) que retorna 1, entao 1+1 = 2. Porque volta?
Esse 2 ainda é só o ff(3)
Como chamaste com ff(7), ele chama: return ff((n - 1)/2) + ff((n+1)/2); que é ff(3) + ff(4)
Esse 2 ainda é só o ff(3)Como chamaste com ff(7), ele chama:
return ff((n - 1)/2) + ff((n+1)/2);que é ff(3) + ff(4)
ff3) + ff(4)
ff(1) + ff(2)
f(1) retorna 1 ff(2) retorna ff(1) que retorna 1.
pmlm desculpa nao esta entendendo o que vc quer me passar mas e pq esta dificil pra mim. Minha dificuldade e essa que quando um lado da recursao retorna 1 termina no outro tb termina nao entendo da onde sai +1.
A) ff(7) = ff(3) + ff(4)
B) ff(3) = ff(1) + ff(2)
C) ff(4) = ff(2)
Substituindo em A:
D) ff(7) = [ff(1) + ff(2)] + ff(2)
E) ff(1) = 1
F) ff(2) = ff(1) (que ja sabemos que é 1)
Substituindo em D:
ff(7) = [1+1]+1 = 3
primeiro nao é executado esse lado return ff((n - 1)/2) + para depois ir para o outro?
Sim, mas isso para perceberes as operações feitas, a ordem é:
ff(7)
ff(3)
ff(1)
ff(2)
ff(1)
ff(4)
ff(2)
ff(1)
Sim, mas isso para perceberes as operações feitas, a ordem é:ff(7)
ff(3)
ff(1)
ff(2)
ff(1)
ff(4)
ff(2)
ff(1)
Hum, então acho que estou começando a entender.
ff(7)
return ff((n - 1)/2) +
ff(3)
return ff((n - 1)/2) +
ff(1)
return 1 - MOOOOORREEU ESSE LADO NÉ?
Vamos para o outro lado
ff(7)
return ff((n + 1)/2) +
Agora nao seria
ff(4) ?
que retornaria ff(n/2)
ff(2)
que retornaria ff(n/2)
ff(1)
return 1 e acabaria aqui?
O que terminou foi o primeiro lado do ff(3) ainda falta o segundo lado do ff(3)
Imagina que tens uma pilha com os ff a calcular.
Colocas ff(7)
Retiras ff(7) e colocas ff(3) + ff(4)
Retiras o ff(3) e colocas ff(1) + ff(2) -> fica ff(1)+ ff(2) + ff(4)
Retiras o ff(1) e sabes que é 1 -> fica 1 + ff(2) + ff(4)
Retiras o ff(2) e colocas ff(1) -> fica 1 + ff(1) + ff(4)
Retiras o ff(1) e sabes que é 1 -> fica 1 + 1 + ff(4)
Retiras o ff(4) e colocas ff(2) -> fica 1 + 1 + ff(2)
Retiras o ff(2) e colocas ff(1) -> fica 1 + 1 + ff(1)
Retiras o ff(1) e sabes que é 1 -> fica 1 + 1 + 1
Não tens mais ff a calcular e tens o resultado 3
Colocas ff(7)
Retiras ff(7) e colocas ff(3) + ff(4)
Retiras o ff(3) e colocas ff(1) + ff(2) -> fica ff(1)+ ff(2) + ff(4)
return ff((n - 1)/2) + ff((n+1)/2);
para n = 3
return ff((n - 1)/2) + ff((n+1)/2);para n = 3
Entao estou entendendo tudo errado entao =/
para todos “n” é executado esssas duas recursoes return ff((n - 1)/2) + ff((n+1)/2); ? não era uma de cada vez? Essa ff((n - 1)/2) depois + essa ff((n+1)/2); ?
Caracoliss entendi agora pml depois de tantas horas lendo e relendo kkk. Muito obrigado viu velho?!
Para todos os n não, só para os ímpares (que não o 1). Para os pares é return ff(n/2)
Entendi pmlm muito obrigado.
Agora eu troquei o exemplo veja só:
package pacote.testando;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class B extends A{
public static void main(String[] args) {
int n = ff(4);
System.out.println(n);
}
public static int ff(int n){
//System.out.println(n);
if(n == 1){
return 1;
}
if((n % 2) == 0){
ff(n/2); // Tirei o return.
}
return ff((n - 1)/2) + ff((n+1)/2);
}
}
ff(4)
ff(2)
ff(1)
return 1.
Depois queo retorno é 1, porque o metodo continua?
Sem o return, o código vai continuar até apanhar um return e vai devolver return ff((n - 1)/2) + ff((n+1)/2); para os pares também.
Entao quando retorna 1 não era pra sair do método?
Não te esqueças que estás a chamar o método dentro do próprio método várias vezes. O return não termina todas as chamadas mas a actual.
Ok entendi isso tb pmlm, estou debugando aqui esse codigo que te passei veja so o que sai:
public static void main(String[] args) {
int n = ff(4);
System.out.println(n);
}
public static int ff(int n){
//System.out.println(n);
if(n == 1){
return 1;
}
if((n % 2) == 0){
ff(n/2); // Tirei o return.
}
return ff((n - 1)/2) + ff((n+1)/2);
}
1º ff(4)
2º ff(2)
3º ff(1) --> retorna 1 acaba essa chamada
Nao teria que voltar pra chamada de ff(2) ?
if((n % 2) == 0){
ff(n/2); // Tirei o return.
}
return ff((n - 1)/2) + ff((n+1)/2);
Não porque esse 1 é o resultado da linha ff(n/2). Como esse resultado não está sendo atribuido a nada, vai "perder-se" e ele vai continuar no ff(4) em baixo onde esta o return
if((n % 2) == 0){ ff(n/2); // Tirei o return. } return ff((n - 1)/2) + ff((n+1)/2);Não porque esse 1 é o resultado da linha ff(n/2). Como esse resultado não está sendo atribuido a nada, vai "perder-se" e ele vai continuar no ff(4) em baixo onde esta o return
Ueh ff(2) nesse caso nao esta empilhado?
Quer dizer entao que o return nesses casos vai servir pra empilhar a chamada atual né?