应该很少听说过尾部递归(Tail Call )和尾部调用(Tail Recursion )，但实际上有什么用呢？ 读了这篇文章就明白了
什么是尾部呼叫
尾部调用(Tail Call )是函数的最后一个操作调用函数，如下所示
//末尾调用
funcf(nint ) int {
if n=0 {
返回0
}
返回(n-1 ) )。
}
//末尾调用
funcf(nint ) int {
if n=0 {
返回0
}
返回(n-1 ) )。
}
//不是末尾调用
funcf(nint ) int {
if n=0 {
返回0
}
返回nf (n-1 ) )。
}
//不是末尾调用
funcf(nint ) int {
if n=0 {
返回0
}
returnf(n-1 ) f (n-2 )。
}
复制代码
尾煤优化
我知道调用函数时会在内存中生成调用记录。 这称为调用帧(call frame )，它保存函数地址和局部变量等信息。 在函数a内部调用函数b时，将在调用记录a上推送调用记录b，并在函数b执行完成后对记录b进行POP调用。 这实际上听起来像调用堆栈
由于末尾调用是函数的最后操作，所以不需要继续保持现在的函数地址和变量等信息，可以用下一个调用函数复用该调用帧。 这就是末尾调用优化(Tail Call Optimization，TCO ) )。
那么，实际上尾煤优化是如何优化的呢？ 答案是在编译时进行优化。 假设有以下代码调用
函数(int )。
a :=1
b :=2
返回(a，b ) )。
}
funcg(a，b int ) {
x :=a 1
y :=b 1
return x y
}
复制代码
没有尾部调用的优化前汇编指令可能如下所示
f； 函数f
ADD ESP，10H； 打开堆栈空间
.
呼叫g； 调用函数g
SUB ESP，10H； 发行版
回复
g； 函数g
ADD ESP，20H； 为了打开堆栈空间，假定函数g所需的堆栈空间比较大
. 业务逻辑
SUB ESP，20H； 发行版
回复
复制代码
通过尾部调用优化的汇编指令可能如下所示
f； 函数f
.
ADD ESP，10H； 打开堆栈空间
.
ADD ESP，10H； 为了开拓堆栈空间，g需要的堆栈空间比f大，所以需要额外开拓堆栈空间，这也是尾调用难以优化的理由
JUMP g； 调用函数g
SUB ESP，20H； 释放堆栈空间
.
回复
g； 函数g
. 业务逻辑
回复
复制代码
如上所述，通过末尾调用的优化可以复用同一堆栈空间，但并不是所有的编程语言都支持这种优化。 例如，JavaScript(ES6，Lua支持末尾调用的优化。 大多数编程语言(如Java和Python )不支持尾部调用优化。 为什么大多数编程语言都不支持尾调用优化？ 答案是复用调用堆栈，这使得程序调试变得困难。 这是因为调用栈的信息将被删除，而尾部调用的优化本身将变得困难
什么是末尾递归
末尾递归(Tail Recursion )是指函数最后的操作调用自身，是末尾调用的特殊情况。 如下所示
//末尾调用
funcf(nint ) int {
if n=0 {
返回0
}
返回(n-1 ) )。
}
复制代码
尾递归优化
我们知道函数调用会分配内存空间。 递归深度越深，分配的内存空间越大，最终导致堆栈内存空间不足，出现堆栈溢出。 到目前为止的例子表明，实现尾部调用的优化是非常困难的。 不同的函数所需的堆栈区域大小不同，但尾部递归优化不同。 由于是调用本身，所以堆栈区域的大小是固定的。 一些编译器专门优化尾部递归，并将尾部递归转换为迭代。 以程序代码为例，如下所示
func main () }
fmt.print ln (fib (10，0，1 ) )/55
}
//末尾递归版的xqdxmg数
funcfib(n，first，second int ) int )
if n==0 {
返回第一
}
返回文件(n-1，second，first second ) )。
}
//假设末尾递归优化的xqdxmg数
funcfib(n，first，second int ) int )
flag:
if n==0 {
返回第一
}
n=n - 1
first，second=second，first second
goto标志
}
//假设末尾递归优化的xqdxmg数
funcfib(n，first，second int ) int )
for {
if n==0 {
返回第一
}
n=n - 1
first，second=second，first second
}
}
复制代码
综上所述，使用支持尾部调用优化或尾部递归优化的编译器时，唯一的萝莉在编写递归函数时应该尽可能地编写尾部递归，剩下的就交给编译器优化了。 如果编译器不支持，请考虑直接在代码级别进行优化，并将递归更改为迭代