尾调用与尾递归

关注
发布于: 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
原文链接:【http://xie.infoq.cn/article/5fb06b11a5d4b15631eaa2153】。文章转载请联系作者。
哈希说

关注
还未添加个人签名 2018.03.08 加入
还未添加个人简介
发布
暂无评论