转自：

尾部递归是一种技巧。函数是指一些会在函数内调用自己的函数，如果在递归函数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成，而且从角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。如果有尾部归递，就只需要叠套一个 stack，因为电脑只需要将函数的 parameter 改变再重新跑一次。例如，可以把上一次函数的输出当作下一次的输入。然而，利用尾部递归最主要的目的，是要优化。例如在  语言中，明确规定必须针对尾部递归作优化。可见尾部递归的作用，是非常依赖于 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; }消除尾部递归