Learn Computer Science programming - C# and C++ Algorithms

 
Fibonacci
Fibonacci numbers are the numbers in the following sequence. 0,1,1,2,3,5,8,13,21,34,55,89,144.... The first two Fibonacci numbers are 0 and 1 and each number after that is the sum of the previous two.
Code
 

Non-Recursive - runs in O(n) time

int fib( int n ) {
int k, f1, f2;
if ( n < 2 ) 
    return n;
else 
{
    f1 = f2 = 1;
    for (k=2; k < n; k ++) 
    {
        f = f1 + f2;
        f2 = f1;
        f1 = f;
    }
return f;
}

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