函数篇（六）：递归函数与性能优化

递归函数的编写思路

很多编程语言都支持递归函数，所谓递归函数指的是在函数内部调用函数自身的函数，从数学解题思路来说，递归就是把一个大问题拆分成多个小问题，再各个击破，在实际开发过程中，某个问题满足以下条件就可以通过递归函数来解决：

• 一个问题的解可以被拆分成多个子问题的解
• 拆分前的原问题与拆分后的子问题除了数据规模不同，求解思路完全一样
• 子问题存在递归终止条件

需要注意的是，编写递归函数时，这个递归一定要有终止条件，否则就会无限调用下去，直到内存溢出。所以我们可以归纳出递归函数的编写思路：抽象出递归模型（可以被复用到子问题的模式/公式），同时找到终止条件。

通过斐波那契数列求解做演示

下面我们就以递归函数的经典示例 —— 斐波那契数列为例，演示如何通过 Go 语言基于上述归纳的思路编写递归函数来打印斐波那契数列。

斐波那契数列的前几个数字是这样的：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

我们可以通过这些数字的排列规律总结出对应的计算公式：

F(1) = 0
F(2) = 1
...
F(n) = F(n-1) + F(n-2)

即从第三个数字开始，对应的数值是前面两个数字的和，其中 n 表示数字在斐波那契数列中的序号，最后一个公式就是递归模型，通过这个公式就可以把求解斐波那契数列的问题拆分为多个子问题来处理：即把求解 F(n) 的值拆分为求解 F(n-1) 和 F(n-2) 两个子问题返回值的和，依次类推，直到到达终止条件：当 n=2 时，返回数值 1，当 n=1 时，返回数值 0。显然这是一个递归处理的过程，我们根据这个思路编写对应的递归函数 fibonacci 实现如下：

func fibonacci(n int) int {
    if n == 1 {
        return 0
    }
    if n == 2 {
        return 1
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

我们可以这么调用这个函数返回指定序号对应的斐波那契数值：

n := 5
num := fibonacci(n)
fmt.Printf("The %dth number of fibonacci sequence is %d\n", n, num)

上述代码的打印的结果是：

The 5th number of fibonacci sequence is 3

函数执行时间与性能优化

递归函数是层层递归嵌套执行的，如果层级不深，比如上面这种，很快就会返回结果，但如果传入一个更大的序号，比如50，就会明显感觉到延迟，我们可以通过计算函数执行时间来做直观的对比：

n1 := 5
start1 := time.Now()
num1 := fibonacci(n1)
end1 := time.Now()
consume1 := end1.Sub(start1).Seconds()
fmt.Printf("The %dth number of fibonacci sequence is %d\n", n1, num1)
fmt.Printf("It takes %f seconds to calculate the number\n", consume1)

n2 := 50
start2 := time.Now()
num2 := fibonacci(n2)
end2 := time.Now()
consume2 := end2.Sub(start2).Seconds()
fmt.Printf("The %dth number of fibonacci sequence is %d\n", n2, num2)
fmt.Printf("It takes %f seconds to calculate the number\n", consume2)

上述代码的打印结果如下：

The 5th number of fibonacci sequence is 3
It takes 0.000000 seconds to calculate the number
The 50th number of fibonacci sequence is 7778742049
It takes 55.804047 seconds to calculate the number

虽然序号只相差了10倍，但是最终体现在执行时间上，却是不止十倍百倍的巨大差别，究其原因，一方面是因为递归函数调用产生的额外开销，另一方面是因为目前这种实现存在着重复计算，比如我在计算 fibonacci(50) 时，会转化为计算 fibonacci(49) 与 fibonacci(48) 之和，然后我在计算 fibonacci(49) 时，又会转化为调用 fibonacci(48) 与 fibonacci(47) 之和，这样一来 fibonacci(48) 就会两次重复计算，这一重复计算就是一次新的递归（从序号48递归到序号1），依次类推，大量的重复递归计算堆积，最终导致程序执行缓慢，我们可以对这个环节进行优化，通过缓存中间计算结果来避免重复计算，从而提升程序性能。

按照这个思路我们来重写下递归函数 fibonacci 的实现：

const MAX = 50
var fibs [MAX]int

func fibonacci(n int) int {
    if n == 1 {
        return 0
    }

    if n == 2 {
        return 1
    }

    index := n - 1
    if fibs[index] != 0 {
        return fibs[index]
    }

    num := fibonacci(n-1) + fibonacci(n-2)
    fibs[index] = num
    return num
}

这一次，我们会通过预定义数组 fibs 保存已经计算过的斐波那契序号对应的数值（序号 n 与对应数组索引的映射关系为 n-1，因为数组索引从下标 0 开始，而这里的斐波那契序号从 1 开始），这样下次要获取对应序号的斐波那契值时会直接返回而不是调用一次递归函数进行计算。调用代码不变，再次执行，通过打印结果耗时对比可以看出，之前执行慢主要是重复的递归计算导致的：

The 5th number of fibonacci sequence is 3
It takes 0.000000 seconds to calculate the number
The 50th number of fibonacci sequence is 7778742049
It takes 0.000001 seconds to calculate the number

这种优化是在内存中保存中间结果，所以称之为「内存缓存技术」，这种内存缓存技术在优化计算成本相对昂贵的函数调用时非常有用。