数据结构&算法之《尾递归》

其实说起来《尾递归》并不算是一种数据结构或者算法，它只是一种另类的执行流程而已。

1.尾调用

我们先来理解下，什么是尾调用？

fun f(x) {
    return g(x)
}

fun f(x) {
    if (x > 0) {
        return m(x)
    }
    return n(x)
}

像上面这样，在函数的最后一步操作返回一个纯粹的另一个函数调用，就叫尾调用。像下面这些都不是尾调用：

fun f(x) {
    let y = g(x)
    return y
}

fun f(x) {
    return g(x) + 1
}

因为他们返回的都不是一个纯粹的函数调用，比如第二个g(x)后面还有+1操作。

2. 尾调用的优势

那么尾调用有什么特殊之处呢？下面我们拿阶乘的🌰来展示下它的优势：
一般的递归阶乘

fun f(n) {
    if (n == 1) return 1
    return n * f(n - 1)
}

简单的演示下递归调用的调用过程是这样的：

f(5)
5 * f(4)
5 * (4 * f(3))
5 * (4 * (3 * f(2)))
5 * (4 * (3 * (2 * f(1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

我们知道，函数调用会在内存中形成一个调用栈，保存调用位置和内部变量等信息；上面的普通递归调用每次递归都会产生新的调用记录，并且由于之前的调用要等到它后面的调用返回后才会返回，所以整个递归调用，要等到最后一个调用能确定返回结果了，才会一层层返回并释放调用栈。

然后，来看下使用尾调用的阶乘：

fun f(n, result) {
    if (n == 1) return result
    return f(n-1, n * result)
}

它的调用过程是这样的:

f(5, 1)
f(4, 5)
f(3, 20)
f(2, 60)
f(1, 120)
120

尾调用递归和普通递归的最大区别就是它不需要保存外层函数的调用栈。对于一些函数式编程语言来说，编译器还会对尾调用做一些优化，不管是在时间，还是空间上都有很大的提升。

从上面两种方式的调用过程来看，他们是有本质区别的，普通的递归调用是自下而上的，即只有最底层确定了结果，才向上一层层返回；而尾递归则是自上而下的，它每次的调用都会携带上一次的计算结果，每次调用都不需要依赖另一次调用的执行环境。

知乎上有人举了个很形象的例子：

// 尾递归
function story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：story() 
// 尾递归，进入下一个函数不再需要上一个函数的环境了，得出结果以后直接返回。
}

// 正常的递归
function story() {
从前有座山，
山上有座庙，
庙里有个老和尚，
一天老和尚对小和尚讲故事：story()，小和尚听了，找了块豆腐撞死了 
// 非尾递归，下一个函数结束以后此函数还有后续，所以必须保存本身的环境以供处理返回值。
}