Fibonacci Numbers (using Scala)

This video looks at Fibonacci numbers as an example of a recursive function that calls itself more than once and demonstrates how the call stack makes that work. It then also shows how there are better ways to solve this particular problem.

This video is part of a series of learning support material for "Introduction to the Art of Programming Using Scala".

[MarkLewis]

The index depends on where you start counting. Since I am doing this for CS, my sequence is zero referenced, not one referenced.

I can't immediately think of an approach that would work without the counter, but I won't rule out that someone has created one. A pure Dynamic Programming approach uses an array so you would only have two arguments, but it uses more memory. There are also some nice approaches that use Scala Streams.

[AndreaAttard]

I changed the else fibStep(n-2, 1, 1) to else fibStep(n-2, 0, 1) and fixed it, thanks

[AndreaAttard]

Every Fibonacci number that is being returned is 1 off, for example fibRecur(50) is printing the 51st Fibonacci number. Also, is there a way to do it without using the counter?, which means that the helper function takes two longs as params, not three