C# – Three Algorithms For Fibonacci Numbers

In the current article I have decided to show three ways of calculating the Fibonacci numbers in C#. The reason for this is, because Fibonacci is usually given as an example for recursion and it is probably the worst way to calculate it. Thus, let’s start with the three ways to calculate it.cs

  • Fibonacci with recursion

The way to calculate the n-th Fibonacci with recursion is pretty straight forward – in order to calculate each number, you should calculate the numbers before and etc, until you get the bottom of the recursion. Then you should make as many recursion calls as needed. Pretty much, to calculate the 35th Fibonacci number, you should be doing above 29 Million calculations. Which has taken my i7 PC about half second. Thus, this is really not the best way!

  • Fibonacci with memoization

Here you do recursion, but you remember the value of each Fibonacci. Thus, instead of 29 Million for 35th Fibonacci you do 37 calculations. And it takes just 0.002 seconds.

  • The fastest Fibonacci

This is actually how everything starts. If you have never heard about recursion and you wanted to calculate Fibonacci, you would simply make a for-loop for it. And swap the values. My PC has carried it out within really quick time, it could not even write it down 🙂

These are the results:

fib

The first two options – with and without memoization are done through one function, where I have an optional boolean parameter “with_memo” for it. Here comes the code of the Fibonacci:

Available also in GitHub here.

Enjoy it!

About

VBA Developer

Tagged with: , , ,