• Recursion

尾递归

尾递归指的是在一个函数的尾位置调用其本身。从形式上来说，只要函数最后的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），即使是上述的尾递归代码，同样会造成堆栈溢出。