尾递归和编译器优化

长平狐 发布于 2013/03/12 13:02
阅读 247
收藏 0

最近看到尾递归,所谓的尾递归wiki解释如下:

尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数,如果在递归函数中,递归调用返回的结果总被直接返回,则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言,而且从编译器角度来说,亦容易优化成为普通循环。这是因为从电脑的基本面来说,所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递,就只需要叠套一个堆栈,因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化,例如在Scheme语言中,明确规定必须针对尾部递归作优化。[1][2]可见尾部递归的作用,是非常依赖于具体实现的。(http://zh.wikipedia.org/wiki/%E5%B0%BE%E9%80%92%E5%BD%92)

举个例子,求一个数的阶乘:

long FactorialCal( long x){ if(x== 1 ) return x; return FactorialCal(x- 1)* x;} long FactorialCal2( int x, int ncount, long lresult){ if(x> ncount) return lresult; return FactorialCal2(x+ 1, ncount, x* lresult);}

FactorialCal就是一般递归,而FactorialCal2则是尾递归调用,因为这种调用总是在函数末尾执行,并且不会用到调用函数里的任何局部变量。所以有些编译器对此进行优化,在被调用函数执行时,直接利用调用函数的堆栈,不需要重新开辟堆栈空间,所以一般不会导致递归中出现的栈溢出。而一般递归因为调用过程中会存储局部变量,所以调用次数太多时就会发生溢出。但是并不是所有编译器都会对尾递归进行优化,一般在函数式编程语言中会优化(可以参考这篇博文:http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/tail-recursion-explanation.html)。而我们使用的c,c++编译器不会对此优化。

这里列举一个利用递归求链表长度的例子:

1 struct Node 2 { 3 int data; 4 Node * pnext; 5 }; 6 class List 7 { 8 private : 9 Node * m_phead; 10 public : 11 List() 12 { 13 m_phead = new Node; 14 m_phead->data = 0 ; 15 m_phead->pnext = NULL; 16 } 17 ~ List() 18 { 19 // .........; 20 } 21 const Node* GetHead() const 22 { 23 return m_phead; 24 } 25 void add(unsigned ncount) 26 { 27 unsigned index; 28 Node *ptail = m_phead; 29 Node *ptemp = m_phead; 30 while(ptemp!= NULL) 31 { 32 ptail = ptemp; 33 ptemp = ptemp-> pnext; 34 } 35 for(index= 0; index<ncount; index++ ) 36 { 37 ptemp = new Node; 38 ptemp->data = index; 39 ptemp->pnext = NULL; 40 41 ptail->pnext = ptemp; 42 ptail = ptemp; 43 } 44 } 45 }; 46 int GetListLen( const Node * plist) 47 { 48 49 if(plist == NULL) 50 return 0 ; 51 return GetListLen(plist->pnext)+ 1 ; 52 } 53 int GetListLen2( const Node *plist, int nlen) 54 { 55 if(plist == NULL) 56 return nlen; 57 return GetListLen2(plist->pnext, nlen+ 1 ); 58 } 59 int main( int argc, char ** argv) 60 { 61 List ltest; 62 ltest.add( 100000 ); 63 64 // int nresult1 = GetListLen(ltest.GetHead()); 65 int nresult2 = 0 ; 66 nresult2 = GetListLen2(ltest.GetHead(),nresult2); 67 // cout<<"nresult1="<<nresult1<<endl; 68 cout<< " nresult2= "<<nresult2<< endl; 69 70 return 0 ; 71 }

上面程序的编译器是g++。List的析构函数这里没有写,因为只是想验证一下,一般递归调用方式和尾递归调用方式下,编译器有没有区别对待。如果编译器能对尾递归进行优化,那么GetListLen2不会产生栈溢出,从而能正确求出链表长度。试验中我们构造了一个拥有1万个节点的链表,而两种递归方式都无法求出其长度(产生栈溢出)。所以编译器并没有对尾递归进行优化。在平时的编程过程中,尽可能的用循环代替递归,可以防止递归调用过程中的栈溢出。

 

 


原文链接:http://www.cnblogs.com/wb-DarkHorse/archive/2012/10/30/2746461.html
加载中
0
wharf_zhang
wharf_zhang
好文。以前真没注意过这个问题。必要时开个-O2就行了,偷懒的好办法。
返回顶部
顶部