Fibonacci com método recursivo

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);
		}
	}	
}

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); }

1 curtida

[quote=Matheus terra]Cara,

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

[/quote]

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

[quote=yurifw][quote=Matheus terra]Cara,

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

[/quote]

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

[/quote]

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

[quote=yurifw][quote=Matheus terra]Cara,

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

[/quote]

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

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

[quote=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); }[/quote]


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:

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…

1 curtida

[quote=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…[/quote]
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

[quote=flashxl][quote=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); }[/quote]


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 :)[/quote]

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! =/

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.

[quote=Rodrigo Sasaki][quote=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…[/quote]
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[/quote]

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!

[quote=Matheus terra][quote=Rodrigo Sasaki][quote=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…[/quote]
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[/quote]

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![/quote]
É mesmo? Então me explique o motivo do fatorial de 0 ser 1 sem ser por definição.

Aí continuamos a conversa

[quote=Rodrigo Sasaki][quote=Matheus terra][quote=Rodrigo Sasaki][quote=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…[/quote]
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[/quote]

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![/quote]
É mesmo? Então me explique o motivo do fatorial de 0 ser 1 sem ser por definição.

Aí continuamos a conversa[/quote]

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.

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í:

1 curtida

[quote=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í:

[/quote]

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

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

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?

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?[/quote]

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

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?

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?[/quote]

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