算法-递归-尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

线性递归：

1
2
3

long Rescuvie(long n) {
  return (n == 1) ? 1 : n * Rescuvie(n - 1);
}

尾递归：

long TailRescuvie(long n, long a) {
  return (n == 1) ? a : TailRescuvie(n - 1, a * n);
}

long TailRescuvie(long n) {
  return (n == 0) ? 1 : TailRescuvie(n, 1);
}

各语言中尾递归优化

因为Python，Java，Pascal等等无法在语言中实现尾递归优化(Tail Call Optimization, TCO)，所以采用了for, while, goto等特殊结构代替recursive的表述。

C语言可以自动尾递归优化。

在没有尾递归优化的语言，如java, python中，鼓励用迭代iteration来改写尾递归；在有尾递归优化的语言如Erlang中，鼓励用尾递归来改写其他形式的递归。