递归 Recursion

递归栈溢出 Recursion Stack Overflow

递归需要栈空间，有时候会栈溢出。

尾递归 Tail Recursion

有些情况下可以用尾递归避免栈溢出。一个function（或subroutine）的最后一步（不一定是最后一行代码）也是一个function的话，就是tail call，如果这个function是自身，就是尾递归。

比如：

def factorial(n):
    def factorial_tail(n, accumulator):
        if n < 0:
            raise ValueError
        if n == 0:
            return accumulator
        return factorial_tail(n - 1, accumulator * n)
    return factorial_tail(n, 1)

某些语言能自动优化尾递归，因为每层递归都相当于把factorial_tail(n, acc)变成了factorial_tail(n - 1, acc * n)，就像数学化简一样。

不过Python是不支持尾递归优化的。Python最多支持1000层递归，你试试factorial(1000)。

当然能用尾递归优化的，基本都能写成循环。

现状是，大部分常用语言都不支持的，Java、JavaScript（V8）、Python都不支持。Scala、Haskell都是自动优化的，Kotlin要加个tailrec修饰符。