著名的斐波拉契数列的非递归源程序

计算斐波拉契数列F(n)
F(n) = n  n = 0,1,2
F(n) = F(n-1) – F(n-3)  n>=3
要求不用递归算法计算 

/* 递归算法 */

unsigned int fn(unsigned int n)
{
 if(n < 3)
 {
  return n;
 }
 else
 {
  return (fn(n - 1) + fn(n - 2));
 }
}

/* 非递归算法 */

#define STACKSZ 100
static unsigned int stack[STACKSZ];
static unsigned int idx;

int push(unsigned int *e)
{
 if(idx < STACKSZ)
 {
  stack[idx ++] = *e;
  return 1;
 }
 else
 {
  return 0;
 }
}

int pop(unsigned int *e)
{
 if(idx > 0)
 {
  *e = stack[-- idx];
  return 1;
 }
 else
 {
  return 0;
 }
}

unsigned int fn2(unsigned int n)
{
 unsigned int res;
 unsigned int cur;
 if(n < 3)
 {
  return n;
 }
 else
 {
  res = 0;
  cur = n;
  while(1)
  {
   if(cur < 3)
   {
    res += cur;
    if(pop(&cur) == 0)
    {
     break;
    }
   }
   else
   {
    cur --;
    push(&cur);
    cur --;
   }
  }  
  return res;
 }
}

 

/* 测试程序 */

void main(void)
{
#define NUM 40
 unsigned int i;

 printf("We will output the xxxxxxx number serial:\n");
 for(i = 0; i < NUM; i++)
 {
  printf("%d ", fn(i));
 }
 printf("\n");
 printf("We will output the xxxxxxx number serial using method 2:\n");
 for(i = 0; i < NUM; i++)
 {
  printf("%d ", fn2(i));
 }
 printf("\n");

}

 

两种解法区别：

递归法：速度慢，但是可读性强，易维护，可以计算序列受堆栈大小限制

非递归法：速度快，声空间（至少减少n个保存现场进栈的ss，pc寄存器值）， 但是代码复杂，可读性差，不易维护，可以计算序列可以控制，但是也不易估算需要堆栈空间的大小