尾递归

Tim Xu bio photo By Tim Xu xiaoxubeii@gmail.com Comment

尾递归指的是在一个函数的尾位置调用其本身。从形式上来说,只要函数最后的return语句返回的是函数本身,那么它就是一个尾递归。
以下是阶乘的尾递归实现:

def fact(n):
    return fact_iter(n, 1)

def fact_iter(n, value):
    if n == 1:
        return value
    else:
        return fact_iter(n-1, n * value)

函数调用本身是栈调用。每当函数调用一次,栈就会增加一层栈帧。每当函数返回,则会减少一层栈帧。由于堆栈有大小限制,所以在递归调用时,递归次数过多会导致堆栈溢出。在这种情况下可以使用尾递归来优化。事实上尾递归和循环迭代的效果是一样的。尾递归在返回时调用其本身,这样编译器或者解释器就可以对尾递归进行优化,使递归本身不管调用多少次只产生一个栈帧,从而避免堆栈溢出。不过大多数编程语言并没有对尾递归进行优化。在这类编程语言下(比如Python),即使是上述的尾递归代码,同样会造成堆栈溢出。