15,916,949 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
 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
 Quote:When interviewer puts out a question, most often than not, he/she expect not a simple, naive answer but a clever and efficient approach. Quote:Under the most circumstances, internet access is not allowed on face-to-face interview and written test. You have a funny way of projecting your own reality to the rest of the world. Using such absolute terms, doesn't make it true. That may be true in your department/company/country/whatever. It does not mean that it is the same everywhere. As a matter of fact, in my neck of the woods, it is fairly common to allow internet access for many technical interviews. I certainly allow it in the ones I conduct, because I said before, I want to test people in real world circumstances not find out if they are good at memorizing certain piece of code that is useless in 99.99% of the work that we do.
 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: 13-Jun-24 10:46 Refresh 1