尾调用与尾递归

用户头像
哈希说
关注
发布于: 2020 年 11 月 28 日
尾调用与尾递归

尾递归 (Tail Call) 和尾调用 (Tail Recursion) 我们应该都很少听过,那么实际上它们有什么用呢?看完这篇文章就知道了



什么是尾调用

尾调用 (Tail Call) 是指函数的最后一步操作是调用函数,如下所示



// 尾调用
func f(n int) int {
if n <= 0 {
return 0
}
return f(n-1)
}
// 尾调用
func f(n int) int {
if n <= 0 {
return 0
}
return g(n-1)
}
// 非尾调用
func f(n int) int {
if n <= 0 {
return 0
}
return n + f(n-1)
}
// 非尾调用
func f(n int) int {
if n <= 0 {
return 0
}
return f(n-1) + f(n-2)
}



尾调用优化



我们知道,函数调用的时候在内存会生成一条调用记录,我们称它为调用桢 (call frame),保存着函数地址和局部变量等信息。如果函数 A 的内部调用了函数 B,那么在调用记录 A 的上方会 PUSH 调用记录 B,当函数 B 执行完成后会 POP 调用记录 B,这听起来其实就是一个调用栈 (call stack)





尾调用由于是函数的最后一步操作,所以不需要在继续保留当前函数地址和变量等信息,它的调用桢可以被下一个调用函数复用,这就是尾调用优化 (Tail Call Optimization,TCO)





那么实际上尾调用优化是怎么进行优化的呢?答案是在编译时进行优化。假设有如下代码调用



func f() int {
a := 1
b := 2
return g(a, b)
}
func g(a, b int) {
x := a+1
y := b+1
return x+y
}



在没有尾调用优化前它的汇编指令可能如下



f ; 函数 f
ADD ESP, 10H ; 开辟栈空间
...
CALL g ; 调用函数 g
SUB ESP, 10H ; 释放
RET

g ; 函数 g
ADD ESP, 20H ; 开辟栈空间,假设函数 g 需要的栈空间比较大
... ; 业务逻辑
SUB ESP, 20H ; 释放
RET



经过尾调用优化后它的汇编指令可能如下



f ; 函数 f
...
ADD ESP, 10H ; 开辟栈空间
...
ADD ESP, 10H ; 开辟栈空间,由于 g 需要的栈空间比 f 大,需要在额外开辟栈空间,这也是尾调用优化难实现的原因
JUMP g ; 调用函数 g
SUB ESP, 20H ; 释放栈空间
...
RET

g ; 函数 g
... ; 业务逻辑
RET



如上所示,通过尾调用优化可以复用同一块栈空间,然而并不是所有的编程语言都支持这种优化,比如 JavaScript(ES6),Lua 支持尾调用优化。而绝大多数编程语言,比如 Java 和 Python 就不支持尾调用优化。为什么绝大多数编程语言都不支持尾调用优化呢?答案在于复用调用栈,这会导致程序难以调试,因为会消除掉调用栈信息,同时尾调用优化本身实现起来就很困难



什么是尾递归



尾递归 (Tail Recursion) 是指函数的最后一步操作是调用自身,是尾调用的特殊情况,如下所示



// 尾调用
func f(n int) int {
if n <= 0 {
return 0
}
return f(n-1)
}



尾递归优化



我们知道函数调用是要分配内存空间的,随着递归深度越来越深,那么分配的内存空间就越大,最终会导致栈内存空间不够用,导致 stack overflow。从之前的例子我们知道要实现尾调用优化是非常困难的,因为不同函数需要的栈空间大小不一样,但是尾递归优化就不一样了,由于是调用自身,所以栈空间大小是固定的。有些编译器会专门针对尾递归优化,将尾递归转换为迭代。用程序代码来举例子,如下



func main() {
fmt.Println(fib(10, 0, 1)) // 55
}
// 尾递归版的斐波那契数
func fib(n, first, second int) int {
if n == 0 {
return first
}
return fib(n-1, second, first+second)
}
// 假设尾递归优化的斐波那契数
func fib(n, first, second int) int {
flag:
if n == 0 {
return first
}
n = n - 1
first, second = second, first+second
goto flag
}
// 假设尾递归优化的斐波那契数
func fib(n, first, second int) int {
for {
if n == 0 {
return first
}
n = n - 1
first, second = second, first+second
}
}



综上,如果你使用的编译器支持尾调用优化尾递归优化,那么当你在写递归函数时应当尽可能写成尾递归,剩下的交给编译器优化就可以了。如果编译器不支持的话,可以考虑在代码层面直接进行优化,将递归改为迭代





发布于: 2020 年 11 月 28 日阅读数: 19
用户头像

哈希说

关注

还未添加个人签名 2018.03.08 加入

还未添加个人简介

评论

发布
暂无评论
尾调用与尾递归