Fibonacci - calculo recursivo

o seu problema acho que está na matemática, e não no código…

F(6) = (F(6) - 1) + (F(6) - 2) = 5 e 4 -> 8 ( Soma do Resultado de F(5) e F(4) )
F(5) = (F(5) - 1) + (F(5) - 2) = 4 e 3 -> 5 ( Soma do Resultado de F(4) e F(3) )
F(4) = (F(4) - 1) + (F(4) - 2) = 3 e 2 -> 3 ( Soma do Resultado de F(3) e F(2) )
F(3) = (F(3) - 1) + (F(3) - 2) = 2 e 1 -> 2
F(2) = (F(2) - 1) + (F(2) - 2) = 1 e 0 -> 1

Isso mesmo. O cálculo é f(n) = f(n-1) + f(n-2). E você calculou f(n) = (n-1)+(n-2)

f(4) = f(3) + F(2)

Como:
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = 1
f(0) = 0
Então:
f(4) = [f(2) + f(1)] + [f(1) + f(0)]
f(4) = [f(2) + 1] + 1 + 0
f(4) = {[f(1) + f(0)] + 1] + 1 + 0
f(4) = 1 + 0 + 1 + 1 + 0
f(4) = 3

me desculpem, mas continuo nao entendendo muito bem esta maneira.

F(6) = (F(6) - 1) + (F(6) - 2) = 5 e 4 -> 8 ( Soma do Resultado de F(5) e F(4) ) 5 e 4, vira 8 como?

a) f(4) = [f(2) + f(1)] + [f(1) + f(0)]
b) f(4) = [f(2) + 1] + 1 + 0
c) f(4) = {[f(1) + f(0)] + 1] + 1 + 0
d) f(4) = 1 + 0 + 1 + 1 + 0
e) f(4) = 3

no passo b, fica f(4) = [f(2) + 1] + 1 + 0 = 4. Ja no passo c, f(4) = {[f(1) + f(0)] + 1] + 1 + 0 = 3. O passo C nao deveria ser f(4) = (([f(1)+1] + f(0))+1]+1+0)=4? Nao entendi pq f(2) fica igual a f(1) + f(0).
Realmente, eu so nao estou conseguindo entender a matematica. Slguem poderia por favor me explicar mais detalhadamente? Uma explicacao bem detalhada ajudaria muito. Quase nao durmo de noite tentando intender essa logica! oO

Aguardo resposta, obrigado

Acho que com esse código fica mais fácil de você entender, a fórmula é a seguinte:

Como a série começa com 1, 1, 2, 3, 5, 8, 13… as duas primeiras posições não requerem cálculo, então você retorna 1, a partir da terceira posição que começam realmente os cálculos:

Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)

Onde N = posição, é muito comum confundir a posição do valor na série com o número, por exemplo, Fibonacci(5) calcula o quinto elemento da série, e não para o “valor 5”.

PS: Em algumas literaturas a série de Fibonacci começa em 0 e em outras começa em 1, isso influencia no retorno, estou assumindo que a série começa com 1 nos exemplos.

public class FibonacciRecursivo {
	
	int calculaFibonacci(int posicao) {
		
		return (posicao<=2 ? 1 : calculaFibonacci(posicao-1) + calculaFibonacci(posicao-2));
		
	}

}

public class TestaFibonacciRecursivo {
	
	public static void main(String[] args) {
		
		FibonacciRecursivo fibo = new FibonacciRecursivo();
		int i = fibo.calculaFibonacci(6);
		
		System.out.println(i); // Imprime o sexto elemento da série (número 8)

	}

}

pessoal, continuo nao intendendo bem, o cimo a formula funciona. intendi que o N tratace da posicao mas, posicao = posicao-1 + posicao-2, isso e muito estranho. Porque por exemplo a posicao 6: posicao 6 = posicao 6-1 + posicao 6-2 = posicao 5 + posicao 4? E assim que calcula? Se nao for, quando que esses sinais de adicao e subtracao entram em acao?

a) f(4) = [f(2) + f(1)] + [f(1) + f(0)]
b) f(4) = [f(2) + 1] + 1 + 0
c) f(4) = {[f(1) + f(0)] + 1] + 1 + 0
d) f(4) = 1 + 0 + 1 + 1 + 0
e) f(4) = 3

Esse exemplo me deichou um tanto confuso pq tentei faze-lo para a posicao 6, mas deu tudo errado. Alguem poderia me explicar melhor a matematica por traz de tudo isso? E depois de explicar a matematica, alguem poderia me dar uma iluminada de como a maquina virtual le tudo isso? Um mini tuto :lol: ’
Desculpe minha burrice, mas ainda nao intendi

A regra é essa:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

DaniloM:

me desculpem, mas continuo nao entendendo muito bem esta maneira.
F(6) = (F(6) - 1) + (F(6) - 2)

Não é assim, na verdade, a fórmula vira isso:

F(6) = F(6-1) + F(6-2) ou F(6) = F(5) + F(4)

Agora, quanto é [color=red]F(5)[/color], pela mesma lógica? E [color=orange]F(4)[/color]?
Acompanhe a decomposição das funções, elas foram ressaltadas com cores iguais.

F(6) = [color=red]F(5)[/color] + [color=orange]F(4)[/color], seguindo a mesma lógica para F(5) e f(4) temos:
F(6) = [color=red]F(5-1) + F(5-2)[/color] + [color=orange]F(4-1) + F(4-2)[/color] então
F(6) = [color=orange]F(4)[/color] + [color=“blue”]F(3) + F(3)[/color] + [color=green]F(2)[/color] seguindo a lógica:
F(6) = [color=orange]F(4-1) + F(4-2)[/color] + [color=“blue”]F(3-1) + F(3-2) + F(3-1) + F(3-2)[/color] + [color=green]F(2-1) + F(2-2)[/color]

F(6) = F(3) + F(2) + F(2) + F(1) + F(2) + F(1) + F(1) + F(0). Sabemos q f(1) = 1 e f(0) = 0, logo
F(6) = [color=blue]F(3)[/color] + [color=green]F(2)[/color] + [color=green]F(2)[/color] + 1 + [color=green]F(2)[/color] + 1 + 1 + 0. Seguindo a lógica de novo
F(6) = [color=blue]F(3-1) + F(3-2)[/color] + [color=green]F(2-1) + F(2-2) + F(2-1) + F(2-2)[/color] + 1 + [color=green]F(2-1) + F(2-2)[/color] + 1 + 1
F(6) = F(2) + F(1) + F(1) + F(0) + F(1) + F(0) + 1 + F(1) + F(0) + 1 + 1
F(6) = [color=green]F(2)[/color] + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1
F(6) = [color=green]F(2-1) + F(2-2)[/color] + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1
F(6) = F(1) + F(0) + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1
F(6) = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1
F(6) = 8

Caramba, agora estou comecando a intender!!! XD Nunca imaginaria que era assim que essa formula funcionava! Bom, a matematica está tranquila, entendi perfeitamente. A duvida agora esta na forma como a JVM le isso:
f(6) = f(6-1) + f(6-2) = [color=red]f(5)[/color] + [color=yellow]f(4)[/color]. Para a cor vermelha, f(5), ele vai iniciar aquele processo de f(5-1) + f(5-2)… depois o f(5) se transforma em duas outras formulas: f(4) + f(3), f(4) vai vira f(4-1) + f(4-2)… e assim por diante. pelo que me parece, varios processos estarao rodando em paralelo, ao mesmo tempo. É isso mesmo?
Digamos que eu tenha adotado o valor 6 como parametro do metodo f quando a JVM ler a instrucao:
return f(n) = f(n-1) + f(n-2) que seria f(6) = f(6-1) + f(6-2) qual valor iria retornar como parametro para o metodo? Sendo que disso iria ficar: f(6) = f(5) + f(4) entao o valor que iria retornar como parametro para o metodo continuar a formula, seria o 5 ou 4? Ou ainda, ele iria iniciar os dois ao mesmo tempo tendo 2 processos em paralelo?

Obs: ViniGodoy, se esse forum tivece sistema de reputacao vc ja teria recebido ela de mim! Brigadao pela ajuda ate aqui. Ainda tenho algumas duvidas, mas elas estarao terminando aos poucos heheheheh
aguardo ancioso a resposta

Edit: Tentei fazer essa formula numa folha e fiz tambem com o numero 7 e deu certo. Entao eu ja intendi a matematica, so falta intender mesmo a logica de como a JVM le isso. Seria por processos paralelos mesmo, né?

tava dando uma pesquisada e fiquei sabendo que quando vc tem processos paralelos, vc tem os threads. E que nesse caso, nao é processo paralelo e sim em serie. Ele executa um e depois o outro né? Guardando na memoria os valores que ainda nao foram utilizados. Certo?

Desculpe perguntar depois de tanto tempo… minha dúvida é a seguinte: no trecho

F(6) = F(5) + F(4)

Em F(5) primeiro a vm vai calcular o F(5) até F(0) somar todos os valores retornar, fazer o mesmo procedimento para F(4) e depois somar os dois valores (F(5) e F(4)) e atribuir à F(6) que este por sua vez vai continuar este processo até ele ser 0 ou 1?

Se for assim este procedimento todo deve consumir bastante memória não?

Isso, veja outro exemplo que respondi há pouco:

Não consome tanta memória assim, embora gaste muito processamento devido a recursão e a repetição de vários cálculos.
Veja no exemplo ali em cima quantas vezes foram calculados f(2), f(3), e f(4)…

Nesse outro exemplo, mostro como otimizar isso através de um cache:

Estava estudando sobre isso agora e, pensando em uma maneira de não usar recursividade e sucessivas trocas de valores entre variáveis para criar uma sequencia, fiz o seguinte:

List<Integer> fib = new ArrayList();
		
fib.add(0);
fib.add(1);
		
for(int i = 0; fib.get(i) < 100; i++){
	fib.add(fib.get(i) + fib.get(i + 1));
}
System.out.println("Fibonacci: " + fib);

Isso é bom, ou da na mesma quanto ao processamento? Como eu poderia fazer com Iterator?

Quanto a processamento, é bem mais eficiente, já que não usa a pilha do SO. Essa é a vantagem de processos iterativos no lugar de recursivos. Outra vantagem é que seu processo evita calcular várias vezes o mesmo fib, do contrário do que ocorre com o método recursivo.

Mas a forma que você escreveu gasta muito mais memória. Se você só precisar calcular um índice específico, seria melhor descartar as sequencias anteriores a i-1 e i-2 e usar 2 variáveis no lugar de uma list inteira.

Entendi!

Obrigada! =)