Next Fibonacci number (non-recursive)

Problem:  Write a non-recursive function to prints the xth Fibonacci number which can do it in linear time


int finNum(int num) {...}


Solution:  The last two problems go into the Fibonacci sequence, so let's start by thinking about how this could be implemented non recursively.


We would need to iterate and always keep track of the two previous numbers, and then finish up with the new Fibonacci number.  And, if we pay attention to error cases, this should be straight forward.


The iteration step needs to be done in the correct order and can be a little tricky, so you may want to write out an example, say 4, and then try it.


So, let's go ahead and implement this:


int fibNum(int num) {

  int i, fib, fib0, fib1;

  /* 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;


  /* Now, write an iterative loop to figure out the fib num */
  /* Intialize fib0 as 0, fib1 as 1, and fib as their sum (1) */
  for (i = 2, fib0=0, fib1=1, fib=1; i < num; i++) {
    fib0 = fib1 + fib;
    fib1 = fib;
    fib = fib0 + fib1;
  }
  
  return fib;
}


Well, that's it.  What's the run time?  Since we go through the lop up to num-2 times, it is num.  We should check boundary cases of num = 2, and an error.  


Also, let's test with the number 5 -- and it works.


So, we have now implemented a non-recursive solution.  Let's talk about the trade-offs.  First, it's longer than the simple fib implementation.  But, it is efficient (linear) and does not have the recursive overhead.


The boundary cases can be tricky, and it doesn't read as nicely as the simple recursive Fibonacci solutions.


This is a problem that seems really easy, but it's important to always check the boundary cases and do an example, as trying to figure out all the fib0, fib1 and fib otherswise and where to initialize the variables, is very tricky otherwise, but fairly simple with an example.


/* Please let me know if you find any bugs or other solutions. */