Pena que a melhor maneira de se calcular Fibonacci é O(log n). Talvez já tenham dado a idéia, mas é só para atiçar a curiosidade.
E o problema da recursividade não é necessariamente a memória e sim o tamanho reservado para a Stack.
O “problema” do fibonacci recursivo é a implementação, se você usar uma recursividade “bem simples” ele vai recalcular todos os valores sempre, pra melhorar isso é só usar um array auxiliar junto com a recursividade, você guarda os valores já calculados no array pra não precisar recalcular pra cada sequencia até atingir a desejada.
[quote=F?io “Kym” Nascimento]O “problema” do fibonacci recursivo é a implementação, se você usar uma recursividade “bem simples” ele vai recalcular todos os valores sempre, pra melhorar isso é só usar um array auxiliar junto com a recursividade, você guarda os valores já calculados no array pra não precisar recalcular pra cada sequencia até atingir a desejada.
Ok isso mesmo
[/quote]
Mas Isso é a memorização já citado e implementado.
vide acima
Primeiramente, esta mais errado ainda, tente fat(n < 0)…
Minha Frase: Boa tarde, segue um exemplo com recursividade. Dá pra melhorar este algoritmo, deixo isso pra vc.
Releia a frase acima e procure se em algum lugar esta escrito que este eh o melhor algoritmo. (tooooma)
Mesmo que ele não trate o valor de entrada igual a zero nao quer dizer que ele esta errado. (tooooma)
Não existe motivos pra calcular o fatorial de zero, isso pode ser verificado na leitura do valor digitado pelo usuário e se for menor ou igual a zero nem precisa chamar o metodo fat(n). (tooooma)
[size=18]Dá pra melhorar este algoritmo, deixo isso pra vcs.[/size]
Só uma dúvida, poquê a melhor maneira de se calcular Fibonacci é O(log n)? Qual a melhor forma de calcular a série de Fibonacci?
[quote=wesley.comput]Primeiramente, esta mais errado ainda, tente fat(n < 0)…
Minha Frase: Boa tarde, segue um exemplo com recursividade. Dá pra melhorar este algoritmo, deixo isso pra vc.
Releia a frase acima e procure se em algum lugar esta escrito que este eh o melhor algoritmo. (tooooma)
Mesmo que ele não trate o valor de entrada igual a zero nao quer dizer que ele esta errado. (tooooma)
Não existe motivos pra calcular o fatorial de zero, isso pode ser verificado na leitura do valor digitado pelo usuário e se for menor ou igual a zero nem precisa chamar o metodo fat(n). (tooooma)
[size=18]Dá pra melhorar este algoritmo, deixo isso pra vcs.[/size]
Só uma dúvida, poquê a melhor maneira de se calcular Fibonacci é O(log n)? Qual a melhor forma de calcular a série de Fibonacci?[/quote]
Ô pessoa, leia o meu comentário. Falei que o algoritmo está errado ( pois está ) e dei um exemplo, agora que se quer que eu corrija para você é pedir demais.
Sim, se uma função está definida para n>=0 ( não existe fatorial de número negativo, andou faltando nas suas aulas? ) e não trata esse caso ela está errada. Não falei que o seu algoritmo era melhor ou pior e sim que está errado. Melhorar não é corrigir ( não a princípio). Se não sabe aceitar críticas, se isole.
A definição de saber se uma função é inútil dado um certo valor não compete fora dela. Já pensou se o nome da função fosse:
int metodoInutilQueVoceDesconheceOQueSejaMasEImportanteParaCalcularOSeuPagamento(int k);
E você tivesse que implementar no seu código? Você tem que saber o que ela faz por dentro ou só o que ela retorna? Não tente me dar aulas de como construir código.
E Fibonacci recursivo é exponencial, usando um caso particular algébrico vira linear e usando-se desse caso algébrico, faz-se um dividir-e-conquistar para tornar-se logarítmico. Agora é só procurar.
Até!
[edits]:pensei mais rápido que escrevi, os edits foram para colocar frases compreensíveis.
int fat (int n) {
if (n < 0)
throw new IllegalArgumentException("Fatorial é uma função definida somente dentro do conjunto dos números naturais.");
else if (n == 0 || n == 1)
return 1;
else
return n * fat(n - 1);
}
int fat (int n) {
if (n < 0)
throw new IllegalArgumentException("Fatorial é uma função definida somente dentro do conjunto dos números naturais.");
else if (n == 0 || n == 1)
return 1;
else
return n * fat(n - 1);
}
[/quote]
Oi, faltou o throws IllegalArgumentException na assinatura do método
Ah é verdade, my bad, achei que não era necessário apenas o handle/declare, não sabia que não precisava nem ir na assinatura do método, boa, aprendi mais uma :oops:
int fat (int n) {
if (n < 0)
throw new IllegalArgumentException("Fatorial é uma função definida somente dentro do conjunto dos números naturais.");
else if (n == 0 || n == 1)
return 1;
else
return n * fat(n - 1);
}
[/code][/quote]
Melhorando...[code]
int fat (int n) {
if (n < 0)
throw new IllegalArgumentException("Fatorial é uma função definida somente dentro do conjunto dos números naturais.");
else if (n == 0 || n == 1)
return 1;
else
return n * fat2(n - 1);
}
private int fat2 (int n) {
if (n == 1)
return 1;
else
return n * fat2(n - 1);
}
[quote=leandronsp]Existe uma classe na API que calcula o fatorial? (típico preguiçoso…)
[/quote]
Não sei se existe… mais é algo tão simples o.O
[code]private class MathUtil {
public static BigInteger fatorial(long n) {
return fatorial(BigInteger.valueOf(n));
}
public static BigInteger fatorial(BigInteger n) {
if (n.compareTo(BigInteger.ZERO) == -1)
throw new IllegalArgumentException("N value cannot be less then zero");
return calculateFatorial(n);
}
private static BigInteger calculateFatorial(BigInteger n) {
return (n.equals(BigInteger.ZERO)) ? BigInteger.ONE :
n.multiply(calculateFatorial(n.subtract(BigInteger.ONE))); // o mesmo que n * (n-1)!
}
}[/code]
bastava o ultimo método, so que colocando um método antes de entrar na recursividade, é possivel fazer teste de concistencia, sem ter q fazer N vezes em um recursividade ^^
