Coding thinking about Fibonacci

#1 Simple Recursion

long long fib(long long n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

Time complexity: < O(2^n) : 1.6^n
Used thinking: a literal representation of the Recurrence formula.



#2 Fast Simple Recursion

const long long MAX = 100;
long long fibResult[MAX];
long long fib(long long n)
{
    if (n <= 1)
        return n;
    else if (fibResult[n] != 0)
        return fibResult[n];
    return fibResult[n] = fib(n - 1) + fib(n - 2);
}

Time complexity: < O(n^2)
Used thinking: 'Memoization'
memorization is a concept in which previously used values are stored and not repeated for the same value.



#3 Simple Iteration

const long long MAX = 100;

long long fibResult[MAX] = { 0, 1 };
long long fib(long long n)
{
    for (int i=2; i<=n; i++)
        fibResult[n] = fibResult[n - 1] + fibResult[n - 2];
    return fibResult;
}

Time complexity: O(n)
Used thinking: 'Memoization' ('Recursion -> Iteration')

#4 Pisano Period Iteration

This method is used in a special situation.
Question. fib(n) % M = ?
If M = 10^k (k > 2), period = 15 x 10^(k - 1)

const long long M = 1000000;
const long long period = M / 10 * 15;
long long fibResult[period] = { 0, 1 };
long long fib(long long n)
{
    for (int i=2; i<period; i++)
    {
        fibResult[n] = fibResult[n - 1] + fibResult[n - 2];
        fibResult[n] %= M;
    }
    return fibResult[n % period];
}

Time complexity: O(period)
Used thinking: 'Memoization' + 'Pisano period'

#5 Matrix Iteration

https://github.com/JAlthea/MyLibrary/blob/master/Fibonacci/fibo.cpp

Time complexity: O(logn)
Used thinking: 'Memoization' + 'Matrix' + 'Divide and conquer'