Fibonacci calculation algorithm

Iterative version:

int fibonacci(int n) {
    if (n < 2)
        return n;
    int prev = 0;
    int last = 1;
    for (int i=2; i<=n; ++i) {
        prev = last;
        last = prev + last;
    }
    return last;
}

The time complexity is O(n) while the space complexity is O(3) or constant.

Recursive version:

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

However, this straightforward solution for Fibonacci is extremely inefficient. Since the computation complexity would be exponential as many text books indicated. An intelligent solution is given below, which is O(n). The origin of this solution is here.

int fib(int n, int p0=0, int p1=1) {
    if (n==0)
        return 0;
    else if (n==1)
        return p1;
    else
        return fib(n - 1, p1, p0 + p1);
}

There are recursive solutions are doing even better than O(n). See this link.