15,921,028 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.

## Comments and Discussions

 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
 Statement of "During interview, remember never to give recursive_fib as an answer because this is not what interviewers are looking out for!" without any further explanation and which, as a person that interviews potential programmers, I find completely false.
 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
 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: 21-Jun-24 6:17 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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