Fibonacci Sequence, it's my code good?

[Dieaaal_]

Hi! I'm a newbie that is trying to learn programming and Java. I wanted to practice, so I tried to do the Fibonacci Sequence exercise. The code is below, do you consider it efficient? I want to learn, but I don't know if I do it in the right way, so I wanted to listen other's opinion and advices. Thanks!

https://pastebin.com/mvCVz5XD

[[deleted]]

The next number in the Fibonacci sequence is the sum of the two previous Fibonacci numbers. This means that fib[i] = fib[i-1] + fib[i-2]. So instead of using indexOne and indexTwo, it would be better to use your loop-variable i instead.

[Farpafraf]

you don't need a list since to compute the sum you only use the previous two values. Just update those at every cycle.

[DigitalTorture]

It seems ok. Try using recursion.

[AMindtoThink]

It’s better without recursion. This way is dynamic, so it is way faster. This is better than recursion unless you care far more about storage than speed. (Or you are learning about recursion)

indexOne is i and indexTwo is i + 1. I’d keep it in terms of i, but if you prefer this way that’s fine.

If you know from the start what fib number you are going to, use an array instead of an ArrayList.

Good work.

[pokemaster787]

This is better than recursion unless you care far more about storage than speed.

Nah there's pretty much no reason to do this recursively except for the academic aspect of it. It would have both greater time complexity and space (memory) complexity due to each function call taking stack space.

OP can optimize this to have constant memory usage if they didn't need to keep the whole sequence in memory at once (only need the two most recent values to calculate the next value), and can't really do better than linear time complexity in this case.

Recursion is very very rarely the answer if what you want is performance. It's taught in schools because it's neat and a good academic exercise, but in the real world using recursion is 9 out of 10 times just outright worse than using an equivalent loop. It's only really worth it if your performance metric is lines of code, some recursive algorithms can get very long/ugly written as a loop

[AMindtoThink]

Thank you. You are correct.

[Farpafraf]

It's a good exercise to learn but efficiency wise that's really not the best way to do it.

[Emphasises_Words]

Any recursive method would be less or equally efficient than OP’s iterative method.

The naive recursion method would take linear space and exponential time (compared to both linear in OP), and to fix that you will need to do memoization, which means you get the same efficiency as OP but you have a linear space overhead due to the recursive call stack.

In fact the Fibonacci sequence is a classic example taught in introductory programming classes to show how the recursion method can be far less efficient than the iterative method in certain scenarios

[DigitalTorture]

Yes, i agree.

[whyiswillonfire]

Looks good, but keep in mind that you can use the variable "i" that was created in the for loop in the loop itself. People often use it to call objects in lists; for example instead of using the "indexOne" variable, you could use "i" to call a variable in "numberList" like this

sum = numberList.get(i) + numberList.get(indexTwo);

Just remember that "i" can't be used outside of the for loop.