General: Fibonacci sequence using a loop versus a recursive function

I recently had a phone interview and one of the technical questions they asked me is how to implement a Fibonacci sequence in code.  I started doing it in a loop but it got complicated so I changed to a recursive function.  Unfortunately, I got stuck with the recursive function and never actually finished it.  So after the phone interview I fired up my Visual Studio 2005 and started coding the Fibonacci sequence using a loop and using a recursive function and see which one is better.  The code below tells me recursive function is the way to go.

static int Fibonacci_Loop(int n)
{
  if (n == 0) return 0;
  if (n == 1) return 1;

  int nMinus2 = 0;
  int nMinus1 = 1;
  int nValue = 1;
  for (int i = 2; i <= n; i++)
  {
    nValue = nMinus1 + nMinus2;
    nMinus2 = nMinus1;
    nMinus1 = nValue;
  }

  return nValue;
}

static int Fibonacci_Recursive(int n)
{
  if (n == 1) return 1;
  if (n == 0) return 0;
  return Fibonacci_Recursive(n – 1) + Fibonacci_Recursive(n – 2);
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s