什么是尾递归?和递归的关系是?
尾递归是递归的一种特殊形式,即在函数的末尾,返回调用该函数的结果,例如下列计算阶乘的函数(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/
最后非常推荐读一下 计算机程序的构造和解释 这本书会讲到包括尾递归在内的,大量改善计算机程序复杂性的基本技巧,上面的例子也摘自本书。
大概是循环式的递归。每次递归更新某些变量,而不是产生更多同级别的调用自身。