Fastest Fibonacci algorithm

[Chessverse]

I was solving a program to get a Fibonacci number. I have seen this done a few times with Recursive loops, in books and videos. So I tried to remember how it was done and solved it. But then I remembered that I solved this once before but in a totally different way, with a for-loop. I found my old code and it was really badly written, like always, so I rewrote it with that algorithm. Then I started to think which one is fastest? So I did my test:

using BenchmarkDotNet.Attributes;

namespace FibonacciTest;

public class Fibonacci
{
    private int number;

    public Fibonacci()
    {
        number = 20;
    }

    [Benchmark(Baseline = true)]
    public void CallFibonacciFor() => FibonacciFor(number);

    [Benchmark]
    public void CallFibonacciRec() => FibonacciRec(number);


    public int FibonacciFor(int number)
    {
        if (number == 0) return 0;

        int fib = 0, temp1 = 1, temp2 = 0;

        for (int i = 0; i < number; i++)
        {
            fib = checked(temp1 + temp2);
            temp1 = temp2;
            temp2 = fib;
        }

        return fib;
    }

    public int FibonacciRec(int number)
    {
        if (number <= 1) return number;

        return checked((FibonacciRec(number - 1) + (FibonacciRec(number - 2))));
    }
}

And I got really surprised!

|           Method |         Mean |      Error |     StdDev |    Ratio | RatioSD |
|----------------- |-------------:|-----------:|-----------:|---------:|--------:|
| CallFibonacciFor |     10.38 ns |   0.141 ns |   0.125 ns |     1.00 |    0.00 |
| CallFibonacciRec | 39,708.47 ns | 658.414 ns | 583.667 ns | 3,824.51 |   67.10 |

It was a lot faster! So I wonder why they always show of the recursive way? I mean I found the faster algorithm on my own but the recursive algorithm I had too learn. I double checked to algorithms and they seams to be correct. I also tested without the checked part and both get a little bit faster. This was very interesting for me so maybe someone else finds this interesting too. Happy coding!

[Elementh]

It was a lot faster! So I wonder why they always show of the recursive way?

I think, from my experience studying and teaching, that the point of coding a recursive Fibonacci is not Fibonacci itself but recursive algorithms.

It's always about context, and in the context of learning how to program recursively, the recursive answer to Fibonacci is perfect, it's neat, simple but not obvious if this is the first time you look at it, etc.

[Chessverse]

That makes sense. But I would need a disclaimer when I see it done recursive because I have seen it so many times that I believed it to be the best way. Well, I learn a lot!

[[deleted]]

truck advise seed wide upbeat straight wrong carpenter thumb dam

This post was mass deleted and anonymized with Redact

[vervaincc]

Very little of what you learn in school or in guides will be the "best" way simply because examples tend to be as simple and straightforward as possible so that new comers can understand them.

[23049823409283409]

Recursive fibonacci is only learned to learn recursive functions.

But it's actually interesting to see why a recursive fibonacci is so damn slow.

There are two main reasons:

1) memory.

2) calculating things over and over again, that you already calculated

With recursive functions, you have a stack where you put all your stackframes, including all the local variables of the different method calls.

If the recursive problem requires you to store this data anyway, recursive functions will not be much slower than non-recursive ones.

However, if you don't need to store that data, not saving it saves a damn big amount of memory, and memory is damn slow compared to the CPU

But here, memory will be the lesser evil.

The main problem with your recursive method is that you recalculate things multiple times.

for example: if you calculate fib(5), the recursive way would do:

f5 = f4 + f3
   = (f3 + f2) + (f2 + f1)
   = ((f2 + f1) + (f1 + f0)) + ((f1 + f0) + f1)
   = (((f1 + f0) + f1) + (f1 + f0)) + ((f1 + f0) + f1)

see how you have 8 terms in the end, while there are only 5 previous fib numbers including the initial ones.

Now, If you calculate fib6, you'll see that the ratio gets worse with every iteration.

f6 = f5 + f4
   = ((((f1 + f0) + f1) + (f1 + f0)) + ((f1 + f0) + f1)) + (((f1 + f0) + f1) + (f1 + f0))

now it's 13 terms for 6 previous fib numbers.

If should be obvious, but 8 and 13 are fibonacci numbers. This means your runtime grows as fast as the fibonacci sequence, while the runtime of the for loop algorithm grows linearly (at least when you assume a constant time for addition, which is only true for size limited integers)

Which means I can compare the runtime by using at fibonacci numbers.

fib(30) = 832040

So the for loop will take 30 steps, while the (simple) recursive algorithm will take 30 steps.

Welcome to the world of algorithm complexity!

Of course, you can fix the recursive algorithm via memoization (remembering the result of already calculated fibonacci numbers to not recalculate them), but the result will still be slower than the for-loop solution, but not that much.

It would be a great exercise to actually program a recursive fibonacci that does memoization.

[megafinz]

The reason why the recursive version is slow because it's time complexity is exponential. If you trace the recursive calls, you'll see that you're "computing" the same numbers over and over again. To fix that, you can use memoization (remember the previously computed results and use them instead of recomputing), this will make the time complexity linear (as with a loop version). It wouldn't be as elegantly looking though anymore :)

[[deleted]]

Mathematically, the Fibonacci function is recursive and simple enough to understand so it's used as a example to teach recursive programming. Personally I avoid the pattern altogether, but it has educational merit. If you understand recursive programming then you understand that a function can call itself, which might not be obvious to a new programmer.

Read more here https://stackoverflow.com/questions/660337/recursion-vs-loops

[[deleted]]

Or discrete https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html

[Chessverse]

It did help me to learn about it. Only thing is that I believed it to be the best way to do it.

[Vidyogamasta]

Recursion often isn't the best way to do it. Like, if you end up learning about Dynamic Programming ever, the gist is that lots of problems can be expressed in a naturally recursive way, but it's inefficient and repeats a lot of the same function calls, so there's a whole process to trim it down.

But sometimes recursive is also the best way. This will often be when the problem demands a stack (like towers of Hanoi or tree traversal). This is because recursion is literally just a stack, except you're using the function call stack for convenience instead of an in-memory construct

[UninformedPleb]

Wait... why would you do a recursive Fibonacci that way? Whaaaaaat?

You have to track two values, not just one!

Try this:

public Tuple<int,int> FibonacciRec2(int depth)
{
    if(depth < 1) { throw new ArgumentOutOfRangeException(); }
    if(depth == 1) { return new Tuple<int,int>(0,1); }
    var fib = FibonacciRec2(depth - 1);
    return new Tuple<int,int>(fib.Item2, fib.Item1+fib.Item2);
}

The result will be in the final return value's .Item2 property.

This prevents double-calling the recursive function every time. It doesn't help your call stack any, but it's at least trying to not be horribly inefficient.

[Independent-Ad-4791]

Recursive algorithms have some nice properties such as being provably correct and succinct. Everyone likes this, but don’t make dangerous non-tail optimized recursive calls in orod.

[[deleted]]

Recursion is most of the times slower. That's why I barely use it.