The Fibonacci Sequence

Problem:  Write a recursive function to prints the xth Fibonacci number.


int finNum(int num) {...}


Solution:  


This is a canonical recursive problem, but can be encountered.  Let's start this problem with a review of the Fibonacci sequence.  This is a sequence of numbers where each number is the sum of the previous two numbers, and the first two numbers in the sequence are 0 and 1.  


A mathematician expresses this as:






Now, let's do an example of the first say, 7, Fibonacci numbers to make sure that we get the pattern:


0
1
1
2
3
5
8


And we could go more.  


Well, with this, it seems set up for recursion.  We have our two base cases, which is if the num is 1 or 2.  And, otherwise, we have the sum of the two previous numbers.


With this, we can code it up, and we need to check for base cases:


int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibNum(num-1) + fibNum(num-2));
}


And, that's it.  Let's do an example, say 7 above, and walk through it to make sure that it works.


It does!


So, this solution works recursively.  What is it's runtime?


Well, it calls fibNum two times more as num grows.  This means that the function is O(2^n).  This is horrible for even small sizes of n.  Wow.  Just awful!


Think about how to make this better, while still recurring.  That's tomorrow's problem. 


/* Please let me know if you find any bugs here.  */