算法趣解之递归思想

数学上有一种运算叫做阶乘，它的计算定义如下：

\[ n ! = 1 × 2 × ··· × n ( n ≥ 1) \]

如果，让你依据上述公式，为阶乘运算写一个函数，你会怎么实现？

我想大部分人会利用循环做乘法，得到阶乘结果。这种方法，我们通常称作递推实现方法。

其实，阶乘的运算还可以通过另一种方式实现，那就是递归实现。我们仔细观察，可以发现，原阶乘计算公式进一步可以化为

\[ \begin{aligned} n ! &= 1 × 2 × ··· × n \\ &= n × (n - 1) ! \\ &( n ≥ 1，1 ! = 1，0 ! = 1)\\ \end{aligned} \]

也就是说， \(n\) 的阶乘可以通过 \(n\) 本身和 \(n – 1\) 的阶乘结果确定；更进一步， \(n - 1\) 的阶乘可以通过 \(n - 1\) 本身和 \(n – 2\) 的阶乘结果确定···最终，这样的推导，会到求 1 的阶乘，而 1 的阶乘是 1 。这时，我们将1的结果逐层回代，最后会得到 \(n\) 的阶乘。

上述递归阶乘算法的实现便可通过Python描述如下：

def factorial(n):
    """
    factorial
     计算一个数的阶乘
    参数：
     n：待求阶乘的整数
    返回：
     阶乘计算的结果
    """
    if n < 0:
        raise ValueError("输入不能为负数。")
    elif n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(4))

"""
输出结果：
24
"""

从上面的实现中，我们可以总结递归实现的两大特点：

第一点，也是程序中最重要的一点，就是“自身调用自身部分”（也就是程序中的第15行）。这部分将当前求解的问题，化简为可以利用自身解决的更小的子问题（在本例中，即是将求 \(n\) 的阶乘转化为 \(n\) 本身和 \(n – 1\) 的阶乘的乘积结果）。这部分的描述，通常是以一个公式的形式呈现，这个公式我们称作“递推公式”。

第二点，为了不让递归程序陷入死循环，因而我们需要为递归程序设置一个出口。通常的实现方式是给定一个初始条件，这个初始条件使得所有递归的中间结果获得确定。（在本例中，便是对 \(n\) 等于 1 或者是 0 的时候，直接给出其阶乘的结果）

递归程序通常看起来比较简洁，也易于理解，但是它的执行效率是极低的。我们来实际看一个例子。

比如，我要计算4的阶乘，上述递归实现的阶乘的计算过程是怎样的呢？

在描述这个过程之前，先补充一下“栈”的概念。栈，是一种数据结构。它对数据的操作只在表的一端（这个部位通常被叫做“栈顶”），并且只支持两种操作，一个是Push操作（用于将数据压入栈顶），一个是Pop操作（将栈顶的元素弹出）。

形象一点，你可以把栈的一个个元素想象成一个个盘子，每次的Push操作就是将盘子放在栈的顶端；而每次的Pop操作便是从栈的顶端取出一个盘子。由此可见，栈是一个“先进后出”的数据结构。

对于递归程序来说，为了获得最终的答案，必须要程序自己维护中间的函数状态（因为代码中并没有像循环一样明确给出）。利用什么样的结构来保存这些信息呢？我们仔细看一下递归函数的一般流程。递归的过程，通常是从待解决的问题，通过递推公式，一层一层地推到已知的初始条件的子问题；然后，在依据已知子问题的解，一层一层返回，最终得到原问题的解。这些中间状态的存取是后存的先取用，先存的后取用，这个和栈的特质完全一致，因而，可以利用栈这种数据结构来维护函数的中间状态。

我们利用上述栈的知识，来看一下 \(factorial(4)\) 的执行过程。

要计算 \(factorial(4)\) , 根据递推公式可以得到 \(factorial(4) = 4 × factorial(3)\) 。为了计算 \(factorial(3)\) ，我们先将当前的函数状态 \(factorial(4)\) 压入栈中保存；

要计算 \(factorial(3)\) , 根据递推公式可以得到 \(factorial(3) = 3 × factorial(2)\) 。为了计算 \(factorial(2)\) ，我们先将当前的函数状态 \(factorial(3)\) 压入栈中保存；

···

以此类推，我们会到达递归的出口，也就是直接给出的factorial(1)的值。然后我们从栈中取出最近一个函数状态 \(factorial(2)\) ，得到 \(factorial(2)\) 等于2；再进一步得到 \(factorial(3)\) 等于6， \(factorial(4)\) 等于24。

计算一个简单的4的阶乘，背后有这么多的栈的操作，看上去非常繁琐。同时，随着数据待求数字的增大，其递归层次也变得更深，而栈的空间是有限的，深层次的递归调用可能会使得栈存储不下，导致栈溢出，程序异常终止。

在可读性方面，递归程序的简洁十分利于理解，但在效率方面，并不如循环递推高效。那递归为什么会存在于算法思想里呢？我想除了易于理解以外，还有一点便是有些问题只能通过递归来实现（比如说“汉诺塔问题”。由于篇幅有限，这里不做讨论，大家可以自己看看）。

递归函数在执行过程比较特殊，对应的其时间复杂度的计算也比较特殊。以上述递归求阶乘为例，介绍一下递归函数时间复杂度的分析。

假设问题规模为 \(N\)，所需的步骤为 \(T( N )\) ，根据代码第 15 行可知，乘法需要1次，递归调用 \(factorial\) 需要 \(T ( N -1 )\) 次；进一步则有递推公式 \(T ( N ) = T ( N – 1 ) + 1\) 。

将此递推下去，可得 \(T ( N ) = T (1) + N – 1\) 。当问题规模为1时，显然只需一步即可。所以 \(T ( N ) = 1 + N – 1 = N\) ，从而时间复杂度为 \(O ( N )\) 。

由此可见，递归函数的时间复杂度分析，可以通过寻找所需步骤的递推公式来分析。

在文章的最后，照例进行总结：

递归简单来说，便是包含有“自身调用自身”的编程实现方法。
递归函数通常分为两大部分：一是递推部分、二是初始条件。
递归的过程，通常是从待解决的问题，通过递推公式，一层一层地推到已知的初始条件的子问题；然后，在依据已知子问题的解，一层一层返回，最终得到原问题的解。
栈是一种数据结构，其特点是“先进后出”。
在计算机中，利用栈保存中间的函数状态，递归从而得以实现。
递归函数的时间复杂度分析，可以通过寻找所需步骤的递推公式来分析。
递归函数简洁，易于理解和实现，但其执行效率不如循环递推。