递归问题思考

由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。
递归是用栈机制实现的，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上
会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有需要额外的时间开销。
所以在深度大时，它的时空性就不好了。
#define LEN 4
char buf[LEN]={'a','b','c','d'};
void print_backward(int pos)
{
  if(pos==LEN)
  {
    printf("me talk\n");
    return;
    }
  printf("%d\n",pos);
  print_backward(pos+1);//递归结束之前，放到栈里面，结束后出栈
  printf("-------------\n");
  printf("*************\n");
  putchar(buf[pos]);
}
int main(int argc,char *argv[])
{
  print_backward(0);
}
结果：0  1  2  3 me talk ----------- ********* d -------- ******** c
-----------******** b ------------********** a

以下是斐波那契数列很好的说明了，当递归层数过多的时间，时间几何级增加了。

#include

int Fibonacci(int n)
{
  if((n==1)||(n==2))
    return n;
  else
    return Fibonacci(n-1)+Fibonacci(n-2);
}

int main(int argc,char *argv[])
{
  time_t cur=time(NULL);
  time(&cur);
  char *curstr=ctime(&cur);
  int i,j;
  i=atoi(argv[1]);//当i超过50的时候，就非常明显了
  for(j=1;j<=i;j++)
  printf("%s : j=%d,Fibonacci=%d\n",curstr,j,Fibonacci(j));
  return 0;
}