Fibonacci com método recursivo

25 respostas
F

Pessoal, fiz o exercício da série Fibonacci no qual consistia o uso do método recursivo. Gostaria de saber se o modo que eu fiz está correto (de acordo com o que o exercício pede). Obrigado :slight_smile:

public class Fibonaccix {

	
	int calculaFibonacci(int a) {		
		if (a == 0) {
			return 0;
		}
		if (a == 1) {
			return 1;
		} else {
			int b = this.calculaFibonacci(a-1) + this.calculaFibonacci(a-2);
			return b;
		}		
	}
}
public class FibonaccixTest {
	
	public static void main(String[] args) {
	
		Fibonaccix fibonacci = new Fibonaccix();
		for (int i = 0; i <= 6; i++) {
			int resultado = fibonacci.calculaFibonacci(i);
			System.out.println(resultado);
		}
	}	
}

25 Respostas

Matheus_terra

Cara,

Você fez duas condições de parada sem necessidade e ainda com as condições erradas.

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

Você concorda comigo que se o parâmetro for igual a 0 (zero), o algoritmo vai pegar vai entrar no seu primeiro if e retorna 0, neh? Mas se você ver na sequencia, o primeiro valor, que no caso é da posição 0, vale 1, ou seja, se o parâmetro é igual a 0 ele tem q retornar 1. Se o parâmetro for igual 1 ele também deve retornar 1, nesse caso ta certo o RETORNO do seu if, mas a condição poderia ser genérica.

E você poderia retornar direto o valor, não precisa atribuir em uma variavel pra depois retorna-la.

Faça assim:

static int fibRecursivo(int a){ if(a <= 2) return 1; else return fibRecursivo(a-1) + fibRecursivo(a-2); }

yurifw

Matheus terra:
Cara,

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

acredito que a sequencia comece com 0 cara:
0, 1, 1, 2, 3, 5, 8, 13, 21 …

Matheus_terra

yurifw:
Matheus terra:
Cara,

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

acredito que a sequencia comece com 0 cara:
0, 1, 1, 2, 3, 5, 8, 13, 21 …

Da uma pesquisadinha melhor então, mas ja adiantando olhe essa imagem:

https://www.google.com.br/search?q=sequencia+de+fibonacci&bav=on.2,or.r_qf.&bvm=bv.45373924,d.eWU&biw=1366&bih=667&um=1&ie=UTF-8&hl=pt-BR&tbm=isch&source=og&sa=N&tab=wi&ei=rmRxUb3RIpKc8gSE9oHgBg#imgrc=b8PReogDPPELSM%3A%3BRFHKBG_kcdCRYM%3Bhttp%3A%2F%2Fwww.uff.br%2Fcdme%2Fpascal%2Fpascal-html%2Fhtml_img%2Ffig_sequencia_fibonacci.jpg%3Bhttp%3A%2F%2Fwww.uff.br%2Fcdme%2Fpascal%2F%3B300%3B282

Rodrigo_Sasaki

yurifw:
Matheus terra:
Cara,

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

acredito que a sequencia comece com 0 cara:
0, 1, 1, 2, 3, 5, 8, 13, 21 …


Começa com 0 mesmo. A sequencia do autor do tópico segue ao pé da letra a fórmula matemática:

F

Matheus terra:
Cara,

Você fez duas condições de parada sem necessidade e ainda com as condições erradas.

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

Você concorda comigo que se o parâmetro for igual a 0 (zero), o algoritmo vai pegar vai entrar no seu primeiro if e retorna 0, neh? Mas se você ver na sequencia, o primeiro valor, que no caso é da posição 0, vale 1, ou seja, se o parâmetro é igual a 0 ele tem q retornar 1. Se o parâmetro for igual 1 ele também deve retornar 1, nesse caso ta certo o RETORNO do seu if, mas a condição poderia ser genérica.

E você poderia retornar direto o valor, não precisa atribuir em uma variavel pra depois retorna-la.

Faça assim:

static int fibRecursivo(int a){ if(a <= 2) return 1; else return fibRecursivo(a-1) + fibRecursivo(a-2); }


Pelo o que eu sei, a série Fibonacci começa com o 0 (no enunciado do exercício o laço for começaria com i = 1, porém, a série começa no 0), por isso pus i = 0, o que eu acho mais correto. Retornar o valor direto é bem mais otimizado do que atribuir numa variável, valeu :slight_smile:

Matheus_terra

Só pra complementar:

Se você começar a sequencia do 0, pra você achar o próximo elemento você tem que somar ele mesmo mais o anterior a ele, nesse caso ficaria (0+(-1)), quanto isso da? -1 neh? -1 está na sequencia? Não!! Então a sequencia começa do 1 mesmo.

Pra você achar o próximo elemento começando do 1, você soma 1+0 que é 1. Já temos a sequencia {1, 1}, some eles que você acha o 2, e assim vai…

Rodrigo_Sasaki

Matheus terra:
Só pra complementar:

Se você começar a sequencia do 0, pra você achar o próximo elemento você tem que somar ele mesmo mais o anterior a ele, nesse caso ficaria (0+(-1)), quanto isso da? -1 neh? -1 está na sequencia? Não!! Então a sequencia começa do 1 mesmo.

Pra você achar o próximo elemento começando do 1, você soma 1+0 que é 1. Já temos a sequencia {1, 1}, some eles que você acha o 2, e assim vai…


Não, leia a fórmula matemática. O retorno no caso de 0 e 1 é dado por definição.

o f(n - 1) + f(n - 2) é aplicado no caso de um n maior do que 1

Matheus_terra

flashxl:
Matheus terra:
Cara,

Você fez duas condições de parada sem necessidade e ainda com as condições erradas.

Vamos a sequencia: 1, 1, 2, 3, 5, 8, 13, 21…

Você concorda comigo que se o parâmetro for igual a 0 (zero), o algoritmo vai pegar vai entrar no seu primeiro if e retorna 0, neh? Mas se você ver na sequencia, o primeiro valor, que no caso é da posição 0, vale 1, ou seja, se o parâmetro é igual a 0 ele tem q retornar 1. Se o parâmetro for igual 1 ele também deve retornar 1, nesse caso ta certo o RETORNO do seu if, mas a condição poderia ser genérica.

E você poderia retornar direto o valor, não precisa atribuir em uma variavel pra depois retorna-la.

Faça assim:

static int fibRecursivo(int a){ if(a <= 2) return 1; else return fibRecursivo(a-1) + fibRecursivo(a-2); }


Pelo o que eu sei, a série Fibonacci começa com o 0 (no enunciado do exercício o laço for começaria com i = 1, porém, a série começa no 0), por isso pus i = 0, o que eu acho mais correto. Retornar o valor direto é bem mais otimizado do que atribuir numa variável, valeu :)

Se você começar a sequencia do 0, o próximo valor será -1, e ai já era a sequencia.

To imaginando os ossinhos de Fibonacci se revirando no túmulo nesse exato momento! =/

F

Não entendi isso que você disse. Para mim, o laço vai começar no 0, então fibonacci.calculaFibonacci(0) vai retornar 0, e depois o laço vai ter i = 1, fibonacci.calculaFibonacci(1) vai retornar 1, depois i = 2, fibonacci.calculaFibonacci(2), que é: fibonacci.calculaFibonacci(2) = fibonacci.calculaFibonacci(2 -1) + fibonacci.calculaFibonacci(2 -2), ou seja, fibonacci.calculaFibonacci(2) = fibonacci.calculaFibonacci(1) + fibonacci.calculaFibonacci(0), e isso vai dar fibonacci.calculaFibonacci(2) = 1 + 0, que vai retornar 1, e por aí vai.

Matheus_terra

Rodrigo Sasaki:
Matheus terra:
Só pra complementar:

Se você começar a sequencia do 0, pra você achar o próximo elemento você tem que somar ele mesmo mais o anterior a ele, nesse caso ficaria (0+(-1)), quanto isso da? -1 neh? -1 está na sequencia? Não!! Então a sequencia começa do 1 mesmo.

Pra você achar o próximo elemento começando do 1, você soma 1+0 que é 1. Já temos a sequencia {1, 1}, some eles que você acha o 2, e assim vai…


Não, leia a fórmula matemática. O retorno no caso de 0 e 1 é dado por definição.

o f(n - 1) + f(n - 2) é aplicado no caso de um n maior do que 1

Eu tenho um grave problema, não gosto de aceitar esse termo “por definição”, tenho que saber por que isso foi definido, e se você observar, o retorno é 1 no caso de a == 0 por que se você for somar o 0 mais o número anterior a ele o resultado é -1!!!

Ou seja, toda definição tem uma explicação! E essa seria a explicação para ela D:

NESSE CASO!

Rodrigo_Sasaki

Matheus terra:
Rodrigo Sasaki:
Matheus terra:
Só pra complementar:

Se você começar a sequencia do 0, pra você achar o próximo elemento você tem que somar ele mesmo mais o anterior a ele, nesse caso ficaria (0+(-1)), quanto isso da? -1 neh? -1 está na sequencia? Não!! Então a sequencia começa do 1 mesmo.

Pra você achar o próximo elemento começando do 1, você soma 1+0 que é 1. Já temos a sequencia {1, 1}, some eles que você acha o 2, e assim vai…


Não, leia a fórmula matemática. O retorno no caso de 0 e 1 é dado por definição.

o f(n - 1) + f(n - 2) é aplicado no caso de um n maior do que 1

Eu tenho um grave problema, não gosto de aceitar esse termo “por definição”, tenho que saber por que isso foi definido, e se você observar, o retorno é 1 no caso de a == 0 por que se você for somar o 0 mais o número anterior a ele o resultado é -1!!!

Ou seja, toda definição tem uma explicação! E essa seria a explicação para ela D:

NESSE CASO!


É mesmo? Então me explique o motivo do fatorial de 0 ser 1 sem ser por definição.

Aí continuamos a conversa

Matheus_terra

Rodrigo Sasaki:
Matheus terra:
Rodrigo Sasaki:
Matheus terra:
Só pra complementar:

Se você começar a sequencia do 0, pra você achar o próximo elemento você tem que somar ele mesmo mais o anterior a ele, nesse caso ficaria (0+(-1)), quanto isso da? -1 neh? -1 está na sequencia? Não!! Então a sequencia começa do 1 mesmo.

Pra você achar o próximo elemento começando do 1, você soma 1+0 que é 1. Já temos a sequencia {1, 1}, some eles que você acha o 2, e assim vai…


Não, leia a fórmula matemática. O retorno no caso de 0 e 1 é dado por definição.

o f(n - 1) + f(n - 2) é aplicado no caso de um n maior do que 1

Eu tenho um grave problema, não gosto de aceitar esse termo “por definição”, tenho que saber por que isso foi definido, e se você observar, o retorno é 1 no caso de a == 0 por que se você for somar o 0 mais o número anterior a ele o resultado é -1!!!

Ou seja, toda definição tem uma explicação! E essa seria a explicação para ela D:

NESSE CASO!


É mesmo? Então me explique o motivo do fatorial de 0 ser 1 sem ser por definição.

Aí continuamos a conversa

Pensei que a definição que estávamos falando era a da sequencia de Fibonacci. Eu realmente lembrei dessa definição do fatorial, não sei AINDA o por que dela, mas eu ainda descubro. Só sei que uma coisa podemos dizer, que sem essa definição todo fatorial recursivo seria 0.

Rodrigo_Sasaki

Só mais uns links caso esteja interessado:

http://www.archimedes-lab.org/nombredormachine.html
http://oeis.org/A000045

Mas caso isso seja melhor pra você, o F(0) = 0 é uma convenção mais moderna. No livro onde foi definida a sequencia, ela começa com F(1) = 1, e não existe F(0).

Se quiser ver a folha original da sequencia, está aí:

Matheus_terra

Rodrigo Sasaki:
Só mais uns links caso esteja interessado:

http://www.archimedes-lab.org/nombredormachine.html
http://oeis.org/A000045

Mas caso isso seja melhor pra você, o F(0) = 0 é uma convenção mais moderna. No livro onde foi definida a sequencia, ela começa com F(1) = 1, e não existe F(0).

Se quiser ver a folha original da sequencia, está aí:

Eu também sou bom em pesquisar e aceitar as coisas como elas são :smiley:

Matheus_terra

Dê uma pesquisada sobre Função Gama, entenda o assunto e você vai ver por que o fatorial de 0 é 1 :smiley:

Rodrigo_Sasaki

Eu não tenho problemas com essas definições.

Se F(1) = 1, então o único valor lógico pra F(0) é 0. Mas novamente, isso é por definição.

Perceba que você cometeu um erro ao questionar a definição da sequencia.

Na sua percepção o valor inicial seria 1, pois 0 + (-1) = -1

Agora a fórmula é: f(n) = f(n - 1) + f(n - 2)

com n valendo 1, temos:

f(1) = f(0) + f(-1). E agora? O que você faz?

Matheus_terra

Eu não tenho problemas com essas definições.

Se F(1) = 1, então o único valor lógico pra F(0) é 0. Mas novamente, isso é por definição.

Perceba que você cometeu um erro ao questionar a definição da sequencia.

Na sua percepção o valor inicial seria 1, pois 0 + (-1) = -1

Agora a fórmula é: f(n) = f(n - 1) + f(n - 2)

com n valendo 1, temos:

f(1) = f(0) + f(-1). E agora? O que você faz?

Se o valor de n for igual a 1, ele não vai pegar 0 + (-1)? Quanto da isso?

Rodrigo_Sasaki

Cara, eu to tentando te explicar da maneira que você definiu.

Pelo que você disse, essa fórmula pode ser aplicada em qualquer número (positivo) e o resultado sairá correto. Por isso você excluiu o 0.

Agora aplique essa fórmula com n = 1, que resultado você tem?

Matheus_terra

Cara, eu to tentando te explicar da maneira que você definiu.

Pelo que você disse, essa fórmula pode ser aplicada em qualquer número (positivo) e o resultado sairá correto. Por isso você excluiu o 0.

Agora aplique essa fórmula com n = 1, que resultado você tem?

A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1

Rodrigo_Sasaki

Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Matheus_terra

Rodrigo Sasaki:
Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Se n é igual a 1, aplicando na fórmula recursiva, você vai ter -1 + 0 neh?

Quanto da isso? ¬¬’

Alt + R > calc > ENTER

Isso ajuda :smiley:

Rodrigo_Sasaki

Matheus terra:
Rodrigo Sasaki:
Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Se n é igual a 1, aplicando na fórmula recursiva, você vai ter -1 + 0 neh?

Quanto da isso? ¬¬’

Alt + R > calc > ENTER

Isso ajuda :D


Isso não quebra a sequencia pra você? Eu estou provando pra você que a sua afirmação quebra a sequencia da mesma maneira que a que você está tentando refutar. Mas parece que você não quer aceitar isso. Tudo bem :slight_smile:

Matheus_terra

Rodrigo Sasaki:
Matheus terra:
Rodrigo Sasaki:
Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Se n é igual a 1, aplicando na fórmula recursiva, você vai ter -1 + 0 neh?

Quanto da isso? ¬¬’

Alt + R > calc > ENTER

Isso ajuda :D


Isso não quebra a sequencia pra você? Eu estou provando pra você que a sua afirmação quebra a sequencia da mesma maneira que a que você está tentando refutar. Mas parece que você não quer aceitar isso. Tudo bem :)

Não entendi o que tu quis dizer ¬¬’

Rodrigo_Sasaki

Matheus terra:
Rodrigo Sasaki:
Matheus terra:
Rodrigo Sasaki:
Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Se n é igual a 1, aplicando na fórmula recursiva, você vai ter -1 + 0 neh?

Quanto da isso? ¬¬’

Alt + R > calc > ENTER

Isso ajuda :D


Isso não quebra a sequencia pra você? Eu estou provando pra você que a sua afirmação quebra a sequencia da mesma maneira que a que você está tentando refutar. Mas parece que você não quer aceitar isso. Tudo bem :)

Não entendi o que tu quis dizer ¬¬’

Eu disse que o fatorial de 0 é 0 e o de 1 é 1 por definição.

Você não concordou.

Você disse que a sequencia não pode começar com 0, porque de acordo com a “regrinha”, se ela for aplicada ao número 0, é retornado um valor que não faz sentido e por esse motivo você disse que a sequencia começa com 1.

Tudo bem, realmente se for aplicada regra ao número 0, o resultado não fará sentido.

Agora por que começa com 1? Eu disse novamente que é por definição. Porque se eu for seguir sua linha de raciocínio. O primeiro número da sequencia é o número onde a fórmula pode ser aplicada, correto? Só que a fórmula não pode ser aplicada ao número 1.

Sem as definições iniciais, a fórmula não pode ser aplicada a número nenhum. Porque invariavelmente, alguma hora você chega no f(1)

Matheus_terra

Rodrigo Sasaki:
Matheus terra:
Rodrigo Sasaki:
Matheus terra:
Rodrigo Sasaki:
Matheus terra:
A fórmula é F(n) = F(n-1) + F(n-2), neh?

Beleza, mas essa fórmula não se equivale a F(n+1) = F(n) + F(n-1)?

Pensando algoritmicamente ou não.

Foi isso que eu quis dizer quando n é igual a 0 o próximo valor seria: 0+(-1) = -1


Claro que equivale, se você quiser achar o F(n + 1), mas eu quero o F(n) e quero que n seja 1.

Como eu faço?

Se n é igual a 1, aplicando na fórmula recursiva, você vai ter -1 + 0 neh?

Quanto da isso? ¬¬’

Alt + R > calc > ENTER

Isso ajuda :D


Isso não quebra a sequencia pra você? Eu estou provando pra você que a sua afirmação quebra a sequencia da mesma maneira que a que você está tentando refutar. Mas parece que você não quer aceitar isso. Tudo bem :)

Não entendi o que tu quis dizer ¬¬’

Eu disse que o fatorial de 0 é 0 e o de 1 é 1 por definição.

Você não concordou.

Você disse que a sequencia não pode começar com 0, porque de acordo com a “regrinha”, se ela for aplicada ao número 0, é retornado um valor que não faz sentido e por esse motivo você disse que a sequencia começa com 1.

Tudo bem, realmente se for aplicada regra ao número 0, o resultado não fará sentido.

Agora por que começa com 1? Eu disse novamente que é por definição. Porque se eu for seguir sua linha de raciocínio. O primeiro número da sequencia é o número onde a fórmula pode ser aplicada, correto? Só que a fórmula não pode ser aplicada ao número 1.

Sem as definições iniciais, a fórmula não pode ser aplicada a número nenhum. Porque invariavelmente, alguma hora você chega no f(1)

Se você começa pelo número 1 o próximo número será 1 correto? Pois você vai somar o 1 com o número anterior dele, que é o 0. A partir daí você vai ter um número crescente.

Criado 19 de abril de 2013
Ultima resposta 19 de abr. de 2013
Respostas 25
Participantes 4