Dota
Setembro 21, 2010, 11:19pm
#1
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]
Dota
Setembro 21, 2010, 11:32pm
#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
pmlm
Setembro 22, 2010, 5:51am
#3
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.
Dota
Setembro 22, 2010, 8:59am
#4
[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?
pmlm
Setembro 22, 2010, 10:39am
#5
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)
Dota
Setembro 22, 2010, 11:12am
#6
[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.
pmlm
Setembro 22, 2010, 11:20am
#7
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
Dota
Setembro 22, 2010, 11:25am
#8
primeiro nao é executado esse lado return ff((n - 1)/2) + para depois ir para o outro?
pmlm
Setembro 22, 2010, 11:29am
#9
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)
Dota
Setembro 22, 2010, 11:40am
#10
[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?
pmlm
Setembro 22, 2010, 1:02pm
#11
Dota:
ff(7)
return ff((n - 1)/2) +
ff(3)
return ff((n - 1)/2) +
ff(1)
return 1 - MOOOOORREEU ESSE LADO NÉ?
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
Dota
Setembro 22, 2010, 1:52pm
#12
[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).
pmlm
Setembro 22, 2010, 1:55pm
#13
return ff((n - 1)/2) + ff((n+1)/2);
para n = 3
Dota
Setembro 22, 2010, 2:14pm
#14
[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); ?
Dota
Setembro 22, 2010, 3:54pm
#15
Caracoliss entendi agora pml depois de tantas horas lendo e relendo kkk. Muito obrigado viu velho?!
pmlm
Setembro 22, 2010, 4:32pm
#16
Para todos os n não, só para os ímpares (que não o 1). Para os pares é return ff(n/2)
Dota
Setembro 22, 2010, 4:39pm
#17
Entendi pmlm muito obrigado.
Dota
Setembro 22, 2010, 4:46pm
#18
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?
pmlm
Setembro 22, 2010, 6:04pm
#19
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.
Dota
Setembro 22, 2010, 10:49pm
#20
Entao quando retorna 1 não era pra sair do método?