转自：http://www.cnblogs.com/candyming/archive/2011/12/04/2275448.html
尾部递归是一种编程技巧。递归函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个 stack，因为电脑只需要将函数的 parameter 改变再重新跑一次。例如，可以把上一次函数的输出当作下一次的输入。然而，利用尾部递归最主要的目的，是要优化。例如在 Scheme 语言中，明确规定必须针对尾部递归作优化。[1][2]可见尾部递归的作用，是非常依赖于 implementation 的。
举例说明，最常用作解说递归函数的形式是计算阶乘，如下例
function factorial(x) if (x = 1) return 1 else return x * factorial(x-1) end if end function
上例中，factorial函数调用了自己，所以这是一递归函数。而且，只在返回指令才调用递归函数，所以这亦是尾部递归(错误，这不是尾部递归，
因为factorial(x-1)算完后还要乘以x)。以上函数很容易可以转化为循环版本：
function factorial(x) returnvalue = 1 while (x != 1) returnvalue = x * returnvalue x = x - 1 end while return returnvalue end function
又例如我们可以替 factorial 设立一个 wrapper function：
function fact(i, acc) if (i == 1) return acc return fact(i-1, acc*i) end function function factorial(x) return fact(x, 1) end function
但是，下列计算斐波那契数列的函数不是尾部递归：
function fibonnacci(x) if (x = 1) return 1 else if (x = 2) return 1 else return fibonnacci(x-1) + fibonnacci(x-2) end if end function
因为上述函数中，调用了自己两次，亦即一函数的运行会导致两个函数的运行，故此不可能在叫呼的同时退出本来的函数，
换句话说，调用自己的时后并未到达运行的尾部。
对于递归函数的使用，人们所关心的一个问题是栈空间的增长。确实，随着被调用次数的增加，某些种类的递归函数会线性地
增加栈空间的使用——不过，有一类函数，即尾部递归函数，不管递归有多深，栈的大小都保持不变。
函数所做的最后一件事情是一个函数调用（递归的或者非递归的），这被称为尾部调用。使用尾部调用的递归
称为尾部递归。
在尾部调用之后除去栈结构的方法称为尾部调用优化。尾部调用优化就是要在尾部进行函数调用时使用下一个
栈结构覆盖当前的栈结构，同时保持原来的返回地址。
尾部递归和迭代的区别： 这个确实很难区分。迭代中不一定有递归，但递归中一定有迭代，可说递归是迭代的一部分。
递归是简单的重复调用自己，而迭代则必须有新值出现，而且这个新值是由旧值得来的。
递归就是一个函数调用自己。尾递归也是递归（一个函数在最末尾的地方调用自己），只不过编译器可能会做优化。一旦优化成功，除了性能的提升之外，还可以避免堆栈溢出的情形。即使无限递归也不会造成溢出。
迭代应该是指多次计算，每次计算都更加的接近最终结果，因此，计算的次数增多了就能得到足够精确的近似值。迭代一般用循环来做，但没有规定不能用其它方法来做。比如，你可以用递归来做迭代。
递归是分割子问题 迭代是把用子问题推出大问题，就像算法里面的 搜索 和动态规划一样。
消除尾部递归（数据结构知识：排序二叉树的内容）
TreeNode *TreeSearch(TreeNode *root,KeyType target) { while(root && target != root->entry.key) if(target < root->entry.key) root=root->left; else root=root->right; return root; }消除尾部递归