最近看到尾递归，所谓的尾递归wiki解释如下：
尾部递归是一种技巧。函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成，而且从角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次。利用尾部递归最主要的目的是要优化，例如在语言中，明确规定必须针对尾部递归作优化。可见尾部递归的作用，是非常依赖于具体实现的。()
举个例子，求一个数的阶乘：
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则是尾递归调用，因为这种调用总是在函数末尾执行，并且不会用到调用函数里的任何局部变量。所以有些编译器对此进行优化，在被调用函数执行时，直接利用调用函数的堆栈，不需要重新开辟堆栈空间，所以一般不会导致递归中出现的栈溢出。而一般递归因为调用过程中会存储局部变量，所以调用次数太多时就会发生溢出。但是并不是所有编译器都会对尾递归进行优化，一般在函数式编程语言中会优化(可以参考这篇博文：)。而我们使用的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() const22 {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 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="< < 上面程序的编译器是g++。List的析构函数这里没有写，因为只是想验证一下，一般递归调用方式和尾递归调用方式下，编译器有没有区别对待。如果编译器能对尾递归进行优化，那么GetListLen2不会产生栈溢出，从而能正确求出链表长度。试验中我们构造了一个拥有1万个节点的链表，而两种递归方式都无法求出其长度(产生栈溢出)。所以编译器并没有对尾递归进行优化。在平时的编程过程中，尽可能的用循环代替递归，可以防止递归调用过程中的栈溢出。
2013/9/2 ps: 感谢一楼的回复，我重新试了一下，对于vs的编译器，在指定优化选项为-O1及以上时，递归深度较大时，尾递归不会崩溃，而一般的递归就不行了，但是还有一个问题没有搞清楚，我看了汇编代码(下图所示，左边为优化后的，后边为没有优化的，可以看到编译器只是对寄存器的读写进行了优化)，发现优化后的汇编里面并没有将尾递归转化成循环，这很奇怪。另外，在StackOverFlow上有人告诉我，判断编译器是否对尾递归进行了优化，你可以在递归里面查看它的局部变量的地址是否改变，如果改变了就没有优化，如果没变则说明优化了，所以我按照这个办法试了一下，但是发现无论是否优化，尾递归里面的局部变量地址都发生了变化。对于gcc编译器，-O2优化选项会优化尾递归。
其他相关内容介绍的博客：
http://blog.csdn.net/liu111qiang88/article/details/9255011
http://blog.csdn.net/gnuhpc/article/details/4368831