15,921,941 members
Articles / Programming Languages / C#
Tip/Trick

# Fibonacci Benchmark

Rate me:
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

Written By
Software Developer (Senior)
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.

 First Prev Next
 To improve Benchmark Patrice T21-Nov-18 12:20 Patrice T 21-Nov-18 12:20
 Re: To improve Benchmark Shao Voon Wong25-Nov-18 14:01 Shao Voon Wong 25-Nov-18 14:01
 tail recursion with O(n) rather than O(2^n) Stefan_Lang12-Nov-18 4:43 Stefan_Lang 12-Nov-18 4:43
 Re: tail recursion with O(n) rather than O(2^n) Shao Voon Wong19-Nov-18 3:15 Shao Voon Wong 19-Nov-18 3:15
 Re: tail recursion with O(n) rather than O(2^n) Stefan_Lang19-Nov-18 22:30 Stefan_Lang 19-Nov-18 22:30
 My vote of 1 F Margueirat8-Nov-18 3:26 F Margueirat 8-Nov-18 3:26
 Re: My vote of 1 Shao Voon Wong9-Nov-18 20:10 Shao Voon Wong 9-Nov-18 20:10
 Re: My vote of 1 F Margueirat13-Nov-18 9:27 F Margueirat 13-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.
 Re: My vote of 1 Shao Voon Wong19-Nov-18 3:19 Shao Voon Wong 19-Nov-18 3:19
 Re: My vote of 1 F Margueirat22-Nov-18 8:17 F Margueirat 22-Nov-18 8:17
 Add a list of results obermd7-Nov-18 9:10 obermd 7-Nov-18 9:10
 maybe fun for investigation, but you can go faster Anibal_Ven7-Nov-18 8:00 Anibal_Ven 7-Nov-18 8:00
 Re: maybe fun for investigation, but you can go faster Shao Voon Wong7-Nov-18 19:04 Shao Voon Wong 7-Nov-18 19:04
 Re: maybe fun for investigation, but you can go faster Stefan_Lang12-Nov-18 0:03 Stefan_Lang 12-Nov-18 0:03
 I fear iterative_fib() gives wrong answer for n=1 Patrice T6-Nov-18 9:44 Patrice T 6-Nov-18 9:44
 Re: I fear iterative_fib() gives wrong answer for n=1 Shao Voon Wong7-Nov-18 17:43 Shao Voon Wong 7-Nov-18 17:43
 Re: I fear iterative_fib() gives wrong answer for n=1 Shao Voon Wong21-Nov-18 1:32 Shao Voon Wong 21-Nov-18 1:32
 add a sample for tail recursion Peter BCKR5-Nov-18 22:52 Peter BCKR 5-Nov-18 22:52
 Re: add a sample for tail recursion Shao Voon Wong5-Nov-18 23:08 Shao Voon Wong 5-Nov-18 23:08
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jun-24 13:29 Refresh 1