By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,052 Members | 1,612 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,052 IT Pros & Developers. It's quick & easy.

Which one is better and why?

P: 7
Is recursive function for calculating Fibonacci series or iterative function is better?
ITERATIVE:
Expand|Select|Wrap|Line Numbers
  1. int fibonacci_iterative(int n)      //Iterative formula for fibonacci series
  2. {
  3.   int f0 = 0;
  4.   int f1 = 1;
  5.   int i, fn;
  6.  
  7.   if (n == 0)
  8.         return 0;
  9.   if (n == 1)
  10.         return 1;
  11.  
  12.   for(i = 2; i <= n; i++)
  13.   {
  14.     fn = f0 + f1;
  15.     f0 = f1;
  16.     f1 = fn;
  17.   }
  18.   return f1;
  19. }
  20.  
RECURSIVE
Expand|Select|Wrap|Line Numbers
  1. int fibonacci_recursive(int nNumber)   //Recursive formula for fibonacci series
  2. {
  3.     if (nNumber == 0)
  4.         return 0;
  5.     if (nNumber == 1)
  6.         return 1;
  7.     return fibonacci_recursive(nNumber-1) + fibonacci_recursive(nNumber-2);
  8. }
  9.  
Oct 25 '09 #1
Share this Question
Share on Google+
1 Reply


Expert 100+
P: 2,398
The stack usage for the iterative function is invariant -- it is the same regardless of the input argument.

The stack usage for the recursive function is proportional to the input value.

The recursive function is smaller and easier to understand.

I haven't done an analysis, but it looks to me like the recursive function will be slower than the iterative function.

Which is "better"? It is a trade-off between these factors. In some contexts, ease of understanding will trump everything else; in other contexts (most notably embedded systems), stack usage trumps everything else.
Oct 26 '09 #2

Post your reply

Sign in to post your reply or Sign up for a free account.