Simple Recursion 之后,我一度把递归当作一种算法。但通过比较 Divide and Conquer 和 Dynamic Programming,我才发现之前的理解有点问题。

一切还是要从 Algorithmic Paradigm 说起:

An algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

算法范式,是在算法的层面上抽象出来的一种更泛化的思想,常用的有:

  • Brute-force search 暴力解法
  • Backtracking 回溯算法
  • Greedy algorithm 贪心算法
  • Divide and conquer 分治法
  • Dynamic programming 动态规划

Divide and Conquer 的基本思路是把复杂的问题分解成多个类似的简单问题,解决之后再组合起来得到最终结果。这种算法有很多应用,比如排序中的 Merge Sort,先将数列分解成单个元素,然后再分别聚合,因为聚合的是已经排好顺序的数组,所以效率会高很多。

对于 DC 来说递归就成为一种很合适的实现方式,因为递归的调用是重复同一套代码逻辑,而 DC 中的子问题和最终问题也都是相似的。然而 DC 有个问题是可能会不断地碰到相同的子问题,如果每次都从头解决一遍会造成很严重的性能问题,举 Fibonacci 的例子来说:

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1

    return fib(n-2) + fib(n-1)

由于重复的子问题太多,这么写最后会得到 O(2^n) 的时间复杂度。

对于这种情况,就需要 Memoization,即缓存中间的计算结果,比如下面这个版本:

from functools import cache

@cache
def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1

    return fib(n-2) + fib(n-1)

而这种解法实际上可以归类到另一种范式:动态规划。

Dynamic Programming 也是把问题划分成一个个小的子问题来解决,它包含两个要素:

  1. 问题的最优解可以看成子问题的最优解的组合
  2. 子问题存在重复的情况,如 Fibonacci 的例子

如果不存在子问题的重复,而只需要求出各个子问题的最优解再合并的话,就变回 Divide and Conquer 而不算是 Dynamic Programming 了,比如 Merge Sort 和 Quick Sort.

动态规划一般有两种实现思路:top-down 和 bottom-up. 上面缓存的写法就是 top-down,相当于把 n 从大到小地解决。而 bottom-up 可以用迭代来实现:

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1

    x, y = 0, 1
    for _ in range(1, n):
        x, y = y, x + y

    return y

此时可以更好地看出来,递归和算法范式并不是同一层面的概念。

那么 Dynamic Programming 可以用递归实现 bottom-up 么?答案是肯定的,用尾递归:

def fib(n, x=0, y=1):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return x + y

    return fib(n - 1, y, x + y)

为什么这样就是 bottom-up 了呢,注意 x 和 y 的变化,是从 0 和 1 开始变化,也就是自底向上地解决了问题。至于尾递归,知乎上这个答案解释得很好:

尾递归,比线性递归多一个参数,这个参数是上一次调用函数得到的结果;

所以,关键点在于,尾递归每次调用都在收集结果,避免了线性递归不收集结果只能依次展开消耗内存的坏处。

因为尾递归需要参数来保存中间结果,所以函数定义不像普通递归那么简洁,有两种方法可以解决,一种是像上面代码中一样使用参数默认值,还有一种就是柯里化,简单来说就是二次封装,在 Python 中可以用 partial 轻松完成:

from functools import partial

f = partial(fib, x=0, y=1)

尾递归的效率很高,因为不需要返回上一级调用,所以不会出现栈溢出的情况。类似 GOTO 关键字,经过优化的汇编代码会直接 JUMP 到下一个调用而不用保留之前的内部信息。

但是这种优化需要编译器的支持,并不是所有语言都会兼容尾递归的优化,比如 Python 一直就没有 TCO(Tail Call Optimization). 从 Guido 叔的解释看,一个重要原因是会影响 Debug 时查看对应的栈信息,但他也给出了一种简化 TCO 实现的写法:与其用一堆 If 分支跳来跳去,可以把 return foo(args) 改写成 return foo, (args, ).

同样,尾递归只是手段,可以用它来实现 Dynamic Programming,也可以用其他的方法,比如迭代(比如 Fibonacci 中迭代的复杂度更低,因为只需要 O(1) 的空间),因为关键在于 Memoization 而不是递归。


References