Go 递归函数

平时我们都是在 main() 等函数里面去调用其他函数。如果一个函数在它自己的函数体内部又调用了它自己,这个函数就叫做 “递归函数(recursive function)”。

递归的执行过程很像拆装 “俄罗斯套娃”:先一层层打开大套娃,直到看见最里面不能再拆的小木偶,再从里往外一层层合拢装回去。

递归函数的语法与条件

为了保证递归函数能够正常停下来,不会像死循环那样一直跑下去,我们在编写递归函数时必须同时满足以下 2 个条件:

  • 具备明确的终止条件:我们在函数开头通常先用 if 语句判断什么时候停下来。一旦满足终止条件,就直接返回确定结果,不再继续调用自己。
  • 参数向终止条件靠近:每次调用自身时,传入的参数不能原地踏步,必须一步步往终止条件的方向变化,这样才能在有限次调用后顺利停下来。

语法:

func 函数名(参数 类型) 返回值类型 {
    if 终止条件 {
        return 基础结果
    }
    return 函数名(变化后的参数)
}

说明:

写递归函数时,进入函数体的第一件事就是先写好 if 终止条件,把最简单的基础情况直接返回。如果不满足终止条件,再改变参数继续调用函数自身。

注意: 在递归调用自身时,千万不要把原参数原样传回去。比如在 sum(n) 内部直接写 sum(n),参数就永远到不了终止条件,程序会一直死循环调用下去。

递归函数示例

下面我们从最基础的 “数字累加” 入手,看看递归函数在运行过程中是怎么一步步算出结果的。

示例 1:计算 1 到 n 的累加和

package main

import "fmt"

// 计算 1 到 n 的累加和
func sum(n int) int {
    if n == 1 {
        return 1
    }
    return n + sum(n-1)
}

func main() {
    res := sum(4)
    fmt.Println(res)
}

运行结果如下。

10

分析:

return n + sum(n-1) 这句代码的意思很直观:要想算出 1 到 n 的总和,只需要用当前的数字 n 加上 “1 到 n-1 的总和” 就可以了。而且每次调用 sum() 时,系统都会单独开辟一小块内存来存当前这一层的参数 n,各层之间的 n 互不干扰。

当 sum(4) 执行到 return 4 + sum(3) 时,明明已经遇到 return 了,为什么函数没有立刻结束呢?这是因为加号右边的 sum(3) 还没算出具体数值,sum(4) 只能先停在这里等待 sum(3) 的结果。往下逐层展开的过程如下:

sum(4) = 4 + sum(3)
sum(4) = 4 + (3 + sum(2))
sum(4) = 4 + (3 + (2 + sum(1)))

当程序一路往下调用到 sum(1) 时,满足了 n == 1 的终止条件并直接返回 1。拿到确定的数值 1 之后,前面暂停等待的每一层就开始从里往外逐层相加返回:

sum(4) = 4 + (3 + (2 + 1))
sum(4) = 4 + (3 + 3)
sum(4) = 4 + 6
sum(4) = 10

可以看到,整个执行过程分为两个阶段:先是一层层往下调用自身的 “递推” 阶段,遇到终止条件后再逐层往回算结果的 “回归” 阶段,这也是 “递归” 这个名字的由来。sum(4) 的完整执行流程如下图所示。

sum(4) 的递推与回归执行流程

如果小伙伴们想亲眼看看这个 “先钻进去、再退出来” 的顺序,可以试着在 sum() 递归调用的前后各加一行打印 n 的代码,运行后观察控制台输出就一目了然了。

另外在实际写这类累加函数时,我们通常会把终止条件写成 if n <= 0 { return 0 },防止误传 0 或负数时跨过终止条件。

除了累加求和之外,数学上的正整数 “阶乘” 也是递归的常见例子。一个正整数 n 的阶乘表示从 1 乘到 n 的积,比如 5 的阶乘就是 120(即 5 * 4 * 3 * 2 * 1)。

示例 2:计算 n 的阶乘

package main

import "fmt"

// 计算 n 的阶乘
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1)
}

func main() {
    fmt.Println(factorial(5))
}

运行结果如下。

120

分析:

在这个例子中,调用 factorial(5) 后,每次往里调用 factorial(n-1) 时参数 n 都会减 1,一步步靠近终止条件 n <= 1。等 n 减小到 1 时直接返回 1,随后再逐层往回相乘得出 120。

为什么这里的终止条件写成了 n <= 1,而不是 n == 1 呢?因为在数学上 0 的阶乘也等于 1,这样写除了能正常处理 0 之外,还能防止调用时误传负数而跨过终止条件,避免陷入无限递归。

无限递归与栈溢出

如果在写递归函数时漏掉了终止条件,程序跑起来会发生什么情况呢?下面我们来看一个反面例子。

示例 3:缺少终止条件导致报错

package main

func countDown(n int) {
    countDown(n - 1)    // 缺少终止条件
}

func main() {
    countDown(3)
}

运行结果如下。

(报错)runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

分析:

在计算机底层,每调用一次函数且还没返回时,系统都需要分配一小块叫做 “栈(stack)” 的临时内存,用来保存当前这一层函数的数据。

上面代码中的 countDown() 漏写了终止条件,会不停地调用自己,很快就把栈内存占满,最终报 stack overflow(栈溢出)错误导致程序崩溃。想要修复这个问题,我们只需在函数开头补上判断,让递归在 n <= 0 时通过 return 语句及时退出就可以了。

func countDown(n int) {
    if n <= 0 {
        return
    }
    fmt.Println(n)
    countDown(n - 1)
}

补上终止条件和打印语句后,调用 countDown(3) 就会依次输出 3、2、1 并正常结束,不会再出现栈溢出。

在实际开发中,对于累加求和、求阶乘这类简单的数学计算,我们直接使用前面学过的 for 循环写起来更直观,执行速度也更快、更省内存。递归真正好用的地方是处理层级深度不固定的树形结构,比如逐层扫描嵌套的多级文件夹,小伙伴们根据实际场景灵活选用即可。

上一篇:

下一篇:

给站长反馈

绿叶网正在不断完善中,小伙伴们如果发现任何问题,还望多多给站长反馈,谢谢!

邮箱:lvyenet@vip.qq.com

「绿叶网」服务号
绿叶网服务号放大
关注服务号,微信也能看教程。
绿叶网服务号