Click here to Skip to main content
15,921,941 members
Articles / Programming Languages / C#
Tip/Trick

Fibonacci Benchmark

Rate me:
Please Sign up or sign in to vote.
4.25/5 (10 votes)
5 Nov 2018CPOL 18.1K   112   5   19
Benchmark of recursive and iterative Fibonacci number generation

Introduction

Fibonacci Sequence is defined as A series of numbers in which each number (Fibonacci number) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc.

Source code of recursive, iterative and tail recursive Fibonacci methods are listed below. They are the same for both C++ and C#. Tail recursive version is contributed by Peter Becker.

C++
int recursive_fib(int n)
{
    if (n < 2)
    {
        return n;
    }
    else
    {
        return recursive_fib(n - 2) + recursive_fib(n - 1);
    }
}

int iterative_fib(int n)
{
    if (n < 2)
        return n;

    int second_fib = 0, first_fib = 1, current_fib = 0; 
    for(int i=2; i<=n; i++)
    {    
        current_fib = second_fib+first_fib;    
        second_fib = first_fib;    
        first_fib = current_fib;  
    }  
    return current_fib; 
}

int tail_recursion_fib(int n, int a = 0, int b = 1)
{
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    return tail_recursion_fib(n - 1, b, a + b);
}

C++ Benchmark Result for Finding Fibonacci of 42

recursive_fib timing: 1051ms
iterative_fib timing:    0ms
tail_recursion_fib timing:    0ms

C# Benchmark Result for Finding Fibonacci of 42

recursive_fib timing:01.179
iterative_fib timing:00.000
tail_recursion_fib timing:00.000

C# timing is just slightly behind C++. We will add a global variable named count to keep track of how many times the recursive method is called for fibonacci of 8.

C++
int count = 0;
int recursive_fib_with_count(int n)
{
    ++count;
    if (n < 2)
    {
        return n;
    }
    else
    {
        return recursive_fib_with_count(n - 2) + recursive_fib_with_count(n - 1);
    }
}

Output is as below:

recursive_fib(8) total number of recursive calls:67

We can see recursive_fib is a very inefficient way of generating Fibonacci. During interview, remember never to give recursive_fib as an answer because this is not what interviewers are looking out for!

Source code is hosted at Github.

History

  • 2018-11-06: First release
  • 2018-11-06: Added Peter Becker's tail recursive version
  • 2018-11-21: Fixed the iterative version when n=1

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Singapore Singapore
Shao Voon is from Singapore. His interest lies primarily in computer graphics, software optimization, concurrency, security, and Agile methodologies.

In recent years, he shifted focus to software safety research. His hobby is writing a free C++ DirectX photo slideshow application which can be viewed here.

Comments and Discussions

 
SuggestionTo improve Benchmark Pin
Patrice T21-Nov-18 12:20
mvePatrice T21-Nov-18 12:20 
GeneralRe: To improve Benchmark Pin
Shao Voon Wong25-Nov-18 14:01
mvaShao Voon Wong25-Nov-18 14:01 
Suggestiontail recursion with O(n) rather than O(2^n) Pin
Stefan_Lang12-Nov-18 4:43
Stefan_Lang12-Nov-18 4:43 
GeneralRe: tail recursion with O(n) rather than O(2^n) Pin
Shao Voon Wong19-Nov-18 3:15
mvaShao Voon Wong19-Nov-18 3:15 
GeneralRe: tail recursion with O(n) rather than O(2^n) Pin
Stefan_Lang19-Nov-18 22:30
Stefan_Lang19-Nov-18 22:30 
GeneralMy vote of 1 Pin
F Margueirat8-Nov-18 3:26
F Margueirat8-Nov-18 3:26 
GeneralRe: My vote of 1 Pin
Shao Voon Wong9-Nov-18 20:10
mvaShao Voon Wong9-Nov-18 20:10 
GeneralRe: My vote of 1 Pin
F Margueirat13-Nov-18 9:27
F Margueirat13-Nov-18 9:27 
When I interview someone for a programmer position, I don't care if they memorized some clever way to solve a known mathematical puzzle which has almost no use in the real world. But it would be useful to know that they can identify that a specific problem can be solved recursively and create an algorithm that deals with it in a recursive way.

I'm more likely to through them a complex process and allow them to use Internet and whatever tools they will have in real life and see how they approach it. In that case, if I asked them to find me the most efficient way to calculate a Fibonacci number and you came up with these, I will smile at you, thank you and tell you "will let you know if you are selected for the next phase".

But if you wrote an implementation of Fast Fibonacci, I will know that you know how to research for a problem's solution and will definitely like to see you in the next phase.
GeneralRe: My vote of 1 Pin
Shao Voon Wong19-Nov-18 3:19
mvaShao Voon Wong19-Nov-18 3:19 
GeneralRe: My vote of 1 Pin
F Margueirat22-Nov-18 8:17
F Margueirat22-Nov-18 8:17 
QuestionAdd a list of results Pin
obermd7-Nov-18 9:10
obermd7-Nov-18 9:10 
Questionmaybe fun for investigation, but you can go faster Pin
Anibal_Ven7-Nov-18 8:00
Anibal_Ven7-Nov-18 8:00 
AnswerRe: maybe fun for investigation, but you can go faster Pin
Shao Voon Wong7-Nov-18 19:04
mvaShao Voon Wong7-Nov-18 19:04 
GeneralRe: maybe fun for investigation, but you can go faster Pin
Stefan_Lang12-Nov-18 0:03
Stefan_Lang12-Nov-18 0:03 
QuestionI fear iterative_fib() gives wrong answer for n=1 Pin
Patrice T6-Nov-18 9:44
mvePatrice T6-Nov-18 9:44 
GeneralRe: I fear iterative_fib() gives wrong answer for n=1 Pin
Shao Voon Wong7-Nov-18 17:43
mvaShao Voon Wong7-Nov-18 17:43 
AnswerRe: I fear iterative_fib() gives wrong answer for n=1 Pin
Shao Voon Wong21-Nov-18 1:32
mvaShao Voon Wong21-Nov-18 1:32 
Suggestionadd a sample for tail recursion Pin
Peter BCKR5-Nov-18 22:52
Peter BCKR5-Nov-18 22:52 
GeneralRe: add a sample for tail recursion Pin
Shao Voon Wong5-Nov-18 23:08
mvaShao Voon Wong5-Nov-18 23:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.