Fibonacci Series with Memoization

Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13 ...

fib(n) = 0                        n = 0
         1                        n = 1
         fib(n - 2) + fib(n - 1)  n > 1

Iterative solution with O(n):

int fib(int n) {
  int t0 = 0, t1 = 1, s = 0;

  if (n <= 1)
    return n;

  for (int i = 2; i <= n; i++) {
    s = t0 + t1;
    t0 = t1;
    t1 = s;
  }
  return s;
}

Recursive solution with O(2^n):

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

This Fibonacci function is an excessive recursion, because the function is calling itself multiple times for the same values. Is there a way to avoid the excessive calls, and just make a call only once, and utilize it in further calls? It is possible, with the help of static / global variables, and a process called memoization. It consists of storing function calls in an array so that they can be used again.

Using memoization and recursion:

int f[10];

int fib(int n) {
  if (n <= 1) {
    f[n] = n;
    return n;
  } else {
    if (f[n - 2] == -1)
      f[n - 2] = fib(n - 2);

    if (f[n - 1] == -1)
      f[n - 1] = fib[n - 1];

    f[n] = f[n - 2] + f[n - 1];
    return f[n - 2] + f[n - 1];
  }
}

int main() {
  /* Initialize the array with -1 values */
  for (int i = 0; i < 10; i++) {
    f[i] = -1;
  }

  printf("%d \n", fib(6));
  return 0;
}