ITPub博客

首页 > IT职业 > IT生活 > 递归与goto (转)

递归与goto (转)

原创 IT生活 作者:gugu99 时间:2007-12-04 08:03:05 0 删除 编辑
递归与goto (转)[@more@]

递归与gotoXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

      written by leezy_2000

 

记得刚开始学习C时,老师和教材都有明训:“千万不要乱用goto语句,否则将导致程序可读性极度下降。但能够极大提高效率地情况,可以考虑使用。”抱着不求有功,但求无过地心思,goto一度被我扔到了垃圾篓。后来随着阅读代码量地增加,我发现goto至少在两个方面可起到改善程序地作用。一是出错处理,二是用来模仿递归。用来做出错处理,在某些特定的场合可以,增强阅读性。用来仿真递归,可以极大的提高程序的性能,但无疑会降低程序的可读性。这篇文章讨论后者。

我们来看一段代码:

 

求n—0范围内,所有整数的累加。

unsigned add( unsigned num)

{

 

  if(num != 0) return num+add(num-1);

  else return 0;

}

使用的时候有:

unsigned c=100;

 

cout<< add(c) <

这段程序简单的很,就是用递归求解,没什么好说。当然效率不会高,尤其num比较大的时候。这种影响是由于过于频繁的函数调用导致的。

 

现在我们来归纳一下这次递归调用的特征:

 

1.  由于递归函数原型一致,所以堆栈中存放的数据类型一致。也就是相当于一个数组。

 

2.  先压栈,增长堆栈大小,达到某个临界条件,开始出栈。并对出栈数据进行累加。出栈的次数当然同压栈的次数一致。

 

为了降低函数调用对性能的影响,我们来仿真这个过程。看如下程序和注释。

 

  unsigned stack[100];//模拟堆栈,假设n为100

bool goback=false; //临界条件

  int i=0; //计数

  int p=c; //p=100

  int num=0; //和

 

  //相当于递归函数的入口

  recurse:

  if( p!=0)//进栈

  {

    stack[i++] = p--;

 

    goto recurse;

  }

  else goback=true; //达到临界条件了

 

  //出栈,求和,从递归中返回

  if( --i >=0 )

  {

    num +=stack[i];

    goto recurse;

  }

 

  这样实现,在空间和时间上都会有较佳的改善,当然前提是要用在恰当的地方。

 

  最后说明一下,这个方法不是我发明的。Microsoft C/C++运行时库中的qsort就是用这种办法实现的。

 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-987763/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3122
  • 访问量
    2245663