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 
[code]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);
}[/code]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.
[code]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
[/code]
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)
[quote=pmlm]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)[/quote]
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)
[quote=pmlm]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)[/quote]
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
[code]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) [/code]
mas da onde ta saindo esse ff(2).
return ff((n - 1)/2) + ff((n+1)/2);
para n = 3
[quote=pmlm] return ff((n - 1)/2) + ff((n+1)/2);
para n = 3[/quote]
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ó:
[code]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);
}
}[/code]
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?