Skip to content

Instantly share code, notes, and snippets.

@edbartley
Created October 4, 2012 17:10
Show Gist options
  • Save edbartley/3835019 to your computer and use it in GitHub Desktop.
Save edbartley/3835019 to your computer and use it in GitHub Desktop.
Two specialized implementations of the Fibonacci sequence
// NOTE: These functions are for a specific seed case of the Fibonacci sequence where fib(0) must equal 1 as
// follows:
// Fib(0) = 1
// Fib(1) = 1
// Fib(n) = Fib(n-1) + Fib(n-2), where n > 1
// Seed values are F0 = 1, F1 = 1
// So the sequence that should be produced by incrementing n (starting at 0) is as follows:
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
long long unsigned fibIt(unsigned target)
{
long long unsigned returnValue;
long long unsigned prior1 = 1;
long long unsigned prior2 = 1;
if(target < 2)
{
return 1;
}
for(unsigned counter = 2; counter <= target; counter++)
{
returnValue = prior1 + prior2;
// Remember n-1 and n-2
prior2 = prior1;
prior1 = returnValue;
}
return returnValue;
}
// Note the recursive function is significantly slower than the non-recursive function above.
long long unsigned fibIt2(unsigned target)
{
if(target < 2)
{
return 1;
}
else
{
return fibIt2(target - 1) + fibIt2(target - 2);
}
}
@edbartley
Copy link
Author

fixed a copy paste error from xcode. I copied the wrong fibIt function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment