Fibonacci

1 1 2 3 5 8 13 etc.

Series of numbers found a lot in nature:
– Number of petals in a flower,
– The number of spirals on a sunflower or pineapple tend to be a Fibonacci number

When we make squares with those widths, we get a nice spiral.

Simple series of numbers where n is composed of n-1 + n-2.

The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, …

The next number is found by adding up the two numbers before it.

012 = 3

0123 = 5

01235 = 8

012358 …

1+1 = 2

1+2 = 3

2+3 = 5

3+5 = 8

5+8 = 13

Here is the list of the first 50th Fibonacci numbers:

144

233

377

610

987

1597

2584

4181

6765

10946

17711

28657

46368

75025

121393

196418

317811

514229

832040

1346269

2178309

3524578

5702887

9227465

14930352

24157817

39088169

63245986

102334155

165580141

267914296

433494437

701408733

1134903170

1836311903

47th: 2971215073 (2 971 215 073) <<< beyond int32 with signed bit: 2 2^31 = 147 483 648

48th: 4807526976 (4 807 526 976) <<<< beyond int32 unsigned! 2^32=4 294 967 296

49th: 7778742049

50th: 12 586 269 025

Storing them in an int32 will overflow as of the 47th element.

Int32 can hold 2^32= 4 billions of values but from [-2b, +2b].

To solve this problem, you can change Fibonacci() to return Int64 or long.

There are many solutions to implement the Fibonacci algo and it’s often used as an introduction to Dynamic Programming:

//--------------- iterative version ---------------------
static int FibonacciIterative(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    int prevPrev = 0;
    int prev = 1;
    int result = 0;

    for (int i = 2; i <= n; i++)
    {
        result = prev + prevPrev;
        prevPrev = prev;
        prev = result;
    }
    return result;
}

As pointed out in this post, the iterative approach is the fastest.

https://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches

Time Complexity: O(N)
Space Complexity: O(N)

//--------------- naive recursive version ---------------------
static int FibonacciRecursive(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}

Time Complexity?

O(N) ? Nope.

Look at the recursive tree.

Each node of the recursive tree has 2 children.

This is because we call 2 times F per F.

The depth is 5.

2^5 –> 2^N which is an exponential time that looks like that:

The Recursive version is slower than the iterative.

https://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches

Recursive Tree

            F(5)
    F(4)            F(3)
F(3)    F(F2)   F(2)    F(1)

F(2)F(1)
etc..

Recursive, optimized solution (memoised)

//--------------- optimized recursive version ---------------------
static Dictionary<int> resultHistory = new Dictionary<int>();

static int FibonacciRecursiveOpt(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (resultHistory.ContainsKey(n))
        return resultHistory[n];

    int result = FibonacciRecursiveOpt(n - 1) + FibonacciRecursiveOpt(n - 2);
    resultHistory[n] = result;

    return result;
}