什么是尾递归？

Question

什么是尾递归？和递归的关系是？

Answer 1

尾递归是递归的一种特殊形式，即在函数的末尾，返回调用该函数的结果，例如下列计算阶乘的函数(Scheme):

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

iter 的末尾，要么返回一个数值(product)要么返回一个对 iter 自己的调用，这就叫尾递归。

尾递归的意义在于，所有的尾递归都可以被编译器简单地优化成普通循环，而不必像通常的递归一样，每次调用都消耗额外的栈空间。这是因为，在递归调用发生时，函数已经运行到了末尾，编译器无需再在栈中维护这个函数的环境，只需简单地用下一个函数调用的环境覆盖当前环境即可。

参考：

• http://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
• http://www.zhihu.com/question/20761771
• http://site.douban.com/196781/widget/notes/12161495/note/262014367/

最后非常推荐读一下 计算机程序的构造和解释 这本书会讲到包括尾递归在内的，大量改善计算机程序复杂性的基本技巧，上面的例子也摘自本书。

Answer 2

大概是循环式的递归。每次递归更新某些变量，而不是产生更多同级别的调用自身。