归纳证明及递归的应用

[luokuning]

TLDR: “要想理解递归则要首先理解递归”，但是这篇文章并不是介绍如何使用递归。相反，更多的是通过利用递归来体验归纳证明所带来的好处。 ps. 最近在看 python 相关的一些东西，因此文章里的示例代码用 python 来实现，简单易懂，应该不会成为阅读这篇文章的障碍。

从数组求和开始

数组求和是非常简单的任务，下面是一段可能顺手就可以写成的求和函数 sum_array:

def sum_loop(S):
    total = 0
    for value in S:
        total += value

    return total

z = [1, 4, 12]
print(sum_loop(z)) # 17

这段代码简洁高效，基于常规思路编写，没有任何问题。

现在让我们换一种思路，考虑几种特殊情况数组（实际上 z 在 python 中叫列表）的求和操作。

首先是不包含任何元素的数组：[]，对这类数组求和可以直接返回 0:

其次是只包含一个元素的数组：[a]，很明显，对只包含一个元素的数组求和，应该直接返回数组中这个唯一的元素，这里是 a:

然后是包含两个元素的数组：[a, b]，求和的值为 a + b:

如果是包含三个元素的数组 [a, b, c] 呢？该如何求和？在回答 a + b + c 之前让我们稍作思考，包含三个元素的数组的和，其实可以拆成两个数组来求和。也就是说 [a, b, c] 的和，等于 [a, b] 求和加上对数组 [c] 的求和。而实际上通过上面的分析，我们已经能够对包含两个元素和只包含一个元素的数组求和了，现在要做的就是把两个数组的求和结果简单的相加。所以我们能够对包含三个元素的数组求和：

那如果数组包含了四个元素呢？同样，对包含四个元素的数组求和，可以拆解为对一个包含三个元素的数组以及对一个仅包含一个元素的数组分别求和再相加：

因为我们已经能够对包含三个元素的数组求和，所以包含四个元素的数组的和也能够计算出来。

依此类推，既然我们能够对包含四个元素的数组求和，说明也能够对包含五个元素的数组求和。如果能对包含五个元素的数组求和，那么就能对包含六个元素的数组求和....... 所以其实际上我们已经能够对包含 n 个元素的数组求和了，这就是归纳证明！

我们把刚刚分析写成对应的代码：

def sum_recursion(S):
    if len(S) == 0:
        return 0

    if len(S) == 1:
        return S[0]

    if len(S) == 2:
        return S[0] + S[1]

    # S[:-1] 相当于是 JavaScript 中的 S.slice(0, -1)
    # S[-1:] 则相当于是 S.slice(-1)
    return sum_recursion(S[:-1]) + sum_recursion(S[-1:])

z = [1, 4, 12]
print(sum_recursion(z)) # 17

为了跟最开始使用循环的求和函数区分，我们给新的函数起名为 sum_recursion。可以看到 sum_recursion 函数体中大部分代码都是对最初分析的包含零个、一个、两个元素的数组进行求和操作，最后一条语句，则是将原数组拆分成两个数组，然后分别再次进行求和，并把各自求和的结果相加。

仔细观察 sum_recursion 函数最后的这条语句：

return sum_recursion(S[:-1]) + sum_recursion(S[-1:])

这里所做的事情，是把原数组拆成两个数组，然后分别递归调用 sum_recursion。第一个数组包含了前 n - 1 个元素，第二个数组只包含最后一个元素，即第 n 个元素。为了能更清晰的看到整个计算过程，我们使用图示来表示对一个包含五个元素的数组求和的过程，也就是 sum_recursion ([a, b, c, d, e]) 的调用栈：

可以看到每次调用 sum_recursion 函数的数组都在不断的缩小自身包含的元素数，直至最后只包含两个元素的那个调用。我们把对包含 0、1、2 个元素的数组求和的操作称为基线条件，而求和的整个过程我们要做的最重要的事情就是只管基线条件的计算，剩下的事情就是把数组不断拆解。

使用 sum_recursion 求和的过程仿佛是在说：”我不管这个数组中有多少个元素，我已经告诉 sum_recursion 这个函数怎么对包含 0、1、2 个元素的数组进行求和了。所以接下来我只管把数组不断拆分然后丢给 sum_recursion，它会计算好所有元素的和给我“。

找最大值

如何用我们刚刚的思路来从数组中找出最大值呢？很简单，我们只需要知道如何从包含 0、1、2 个元素的数组中找出最大值：

下面就是从数组中找出最大值的函数实现代码：

def find_max(S):
    if len(S) == 0:
        return None

    if len(S) == 1:
        return S[0]

    if len(S) == 2:
        return S[0] if S[0] > S[1] else S[1]

    left_max = find_max(S[:-2])
    right_max = find_max(S[-2:])

    return left_max if left_max > right_max else right_max

z = [1, 3, 123, 54, 231, 13]
find_max(z) # 231

你可能会想，其实一个循环就能解决数组求和与找最大值问题，为什么还要大费周折写这么多代码来实现呢？仔细想想，在 find_max 函数中，我们做的最复杂的事情，就是从包含两个元素的数组中找出最大值。归纳证明加上递归的应用能够极大的降低我们的心智负担，接下来看看一个稍微复杂的应用场景。

排序

给数组排序是一个经常被讨论的问题，目的很简单，就是把一个乱序的数组排列成非递减的数组。能利用归纳证明的思路来解决排序问题吗？要想知道答案，先从基线条件开始。

如果一个数组不包含任何元素，我们不需要排序，直接返回原空数组：

如果数组只包含一个元素，也不需要排序，直接返回原数组：

如果数组包含两个元素，通过简单的把第一个元素跟第二个元素做一个对比，就能得到排好序的数组：

如果数组包含三个元素，该怎么处理？回想一下，我们现在已经具有了给包含 0、1、2 个元素的数组进行排序的能力，如果能够把包含三个元素的数组拆分成多个包含两个元素的数组，或者仅包含一个元素的数组，然后分别对这些子数组进行排序，再将数组拼接起来不就得到三个元素都排好序的数组了吗？

那么接下来的问题就是，怎么合适的拆分子数组，才能使最后对子数组进行拼接的时候，得到的大的数组是按顺序排列的呢？一个容易想到的方案是，我们以数组的第一个元素 a 作为标准，把小于等于 a 的元素放到一个新数组 S1，把大于 a 的元素统统放到新数组 S2，我们只要对 S1 和 S2 排序，然后通过 S1 + [a] + S2 拼凑成一个新数组，而这个新数组正是符合我们期望排序的数组。

假如我们要排序的数组是 [4, 13, 10]，那么对应的会产生：

S1， S2 分别是一个空数组，及一个包含两个元素的数组，而我们恰好都能够对这两个数组进行排序！

如果命名我们的排序函数为 sort，那么意味着：

# 在 python 中我们能直接使用 + 来拼接两个数组（列表 list）
sort([4, 13, 10]) = sort([]) + [4] + sort([13, 10])

假如我们要排序的数组是 [13, 4, 21] 呢？很明显，S1 = [4], S2 = [21]，sort 函数完全能处理只包含一个元素的数组：

sort([13, 4, 21]) = sort([4]) + [13] + sort([21])

现在我们具有了对包含三个元素的数组进行排序的能力，那包含四个元素的数组呢？比如数组 [5, 23, 9, 12]？

太简单了：

sort([5, 23, 9, 12]) = sort([]) + [5] + sort([23, 9, 12])

好了，接下来就是归纳证明闪光的时刻：既然我们能对包含四个元素的数组排序，说明我们一定能对包含五个元素的数组排序，因此也一定能够对包含六个元素的数组排序........

根据上面思路实现的 sort 函数代码极其简单，唯一比 sum_recursion 及 find_max 函数复杂的地方可能就是 sort 函数中多了一个循环，用来将数组拆分成两个子数组：

def sort(S):
    if len(S) < 2:
        return S

    if len(S) == 2:
        return [S[1], S[0]] if S[0] > S[1] else S

    S1 = []
    S2= []
    for i in range(1, len(S)):
        if S[i] <= S[0]:
            S1.append(S[i])
        else:
            S2.append(S[i])

    return sort(S1) + [S[0]] + sort(S2)

z = [23, 4, 78, 123, 56, 12]
print(sort(z)) # [4, 12, 23, 56, 78, 123]

如果说在之前的数组求和及找最大值中使用归纳证明加递归，有种杀鸡用牛刀的感觉的话，那么其在数组排序中的应用是一个极好的例子，完美展现了归纳证明及递归强大的解决问题的能力。使用得当的话，能大大减少我们处理问题的复杂度。

实际上，上面的 sort 函数就是快速排序的一种实现。

分析

我们再来回顾下 sum_recursion 函数。通过代码可以发现，sum_recursion 其实是一个二路递归函数（binary recursion）。也就是说每次调用 sum_recursion 函数，都会引起两个其他递归函数的调用（这里是 sum_recursion 自己），所以对于性能的影响要格外注意。

而通过上面调用栈的示意图我们知道，sum_recursion 调用会引起大约 2n - 3 个自身调用，而每个 sum_recursion 调用又会复制一遍数组， 所以 sum_recursion 的时间复杂度为 O(n²)。

我们对 sum_recursion 最后一个语句做一个小小的改动：

return sum_recursion(S[:-2]) + sum_recursion(S[-2:])

注意到了吗？两个 -1 变成了 -2。对应的改变就是，每次拆分数组的时候，把前 n-2 个元素分为一组，第 n - 1 跟 n 这两个元素拆分成另一组。相应的，sum_recursion ([a, b, c, d, e]) 的调用栈将变成下面这样：

对于 len(S) == n 的数组来讲，sum_recursion(S) 函数调用现在会引起大约 n 个函数的调用，虽然好于之前的 2n - 3，但是复杂度还是 O(n²)，远远比普通循环或者递归的求和要慢，因此不要将文章中实现的 sum_recursion 及 find_max 函数用于实际项目中。

总结

通过合理的利用递归，我们可以很好的实践归纳证明，并且享受它为解决问题所带来的便利。