## 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.

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`

.

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