Skip to content

Instantly share code, notes, and snippets.

@mdciotti
Created September 12, 2016 18:48
Show Gist options
  • Save mdciotti/c302e524fafeb67889524ffe4cb6d500 to your computer and use it in GitHub Desktop.
Save mdciotti/c302e524fafeb67889524ffe4cb6d500 to your computer and use it in GitHub Desktop.
Fibonacci Number Generators
// 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment