1.1.1　使用递归

为对递归的工作原理有所认识，下面来看一个简单的递归算法：计算阶乘。阶乘可使用下面的函数定义：

f(N) = 1 × 2 × 3× …× (N − 1) × N

换而言之，N的阶乘就是整数1～N的乘积。对于上面的函数，可改写成下面这样：

f(N) = N × (N − 1)× …× 3 × 2 × 1

并进一步改写为下面这样：

f(N) = N × f(N − 1)

上面使用f本身定义了f的阶乘，这就是递归。调用f(N)将导致调用f(N − 1)，进而导致调用f(N − 2)，以此类推。然而，在什么情况下停止递归呢？为此，需要将f(1)定义为1，为递归指定终点。

下面演示如何使用Python来实现递归的阶乘函数：

def factorial(N):
❶   if N == 1:
        return 1
    else:
      ❷ return N * factorial(N- 1)

在❶处，处理了N为1的情形——直接返回1；在❷处，实现了递归调用：调用函数factorial()，并传入参数N − 1。这个函数将不断调用自身，直到N为1。这样做的效果是，当这个函数返回时，就计算出了整数1～N的乘积。

一般而言，实现使用递归的算法时应采取如下步骤。

1．定义一个基线条件（base case）。满足基线条件时，递归将终止。阶乘的基线条件是factorial(1)=1。

2．定义递归步骤。为此，需要考虑如何将算法表示为递归过程。在有些算法中，可能需要执行多次递归调用（稍后将介绍）。

解决可分解为其小型版本的问题时，递归是一个很有用的工具。可用于阶乘算法，也可用于科赫雪花的绘制。然而，递归并非总是效率最高的问题解决方式，在有些情况下，合理的选择是以循环的方式重新实现递归算法。但相比于循环实现，递归算法通常更紧凑、更优雅。