Fibonacci Number Generators

fib.cpp

// Recursive 1
int rFibNum(int a, int b, int n)
{
  if (n == 1)
    return a;
  else if (n == 2)
    return b;
  else
    return rFibNum(a, b, n - 1) + rFibNum(a, b, n - 2);
}

// Simple recurisve
int rFibNum2(int n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  return rFibNum2(n - 1) + rFibNum(n - 2);
}

// Memoized recursive
int[] memo = new int[1000];
int[0] = 0;
int[1] = 1;
int last_n = 1;
int rmFibNum(int n)
{
  if (n <= last_n) return memo[n];
  memo[n] = rmFibNum(n - 1) + rmFibNum(n - 2);
  last_n = n;
  return memo[n];
}

// Iterative
int iFibNum(int n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;
  int a = 0;
  int b = 1;
  int t;
  for (int i = 2; i < n; i++) {
    t = b;
    b = a + b;
    a = t;
  }
  return b;
}

// O(1) Closed form
double phi = (1.0 + sqrt(5)) / 2.0;
double psi = (1.0 - sqrt(5)) / 2.0;
int FibNum(int n)
{
  return (int) (pow(phi, n) - pow(psi, n)) / (phi - psi);
}