Question

4.4.递归的三定律

像阿西莫夫机器人，所有递归算法必须服从三个重要的定律：

1. 递归算法必须具有基本情况。
2. 递归算法必须改变其状态并向基本情况靠近。
3. 递归算法必须以递归方式调用自身。

让我们更详细地看看每一个定律，看看它如何在 listsum 算法中使用。首先，基本情况是算法停止递归的条件。基本情况通常是足够小以直接求解的问题。在listsum 算法中，基本情况是长度为 1 的列表。

为了遵守第二定律，我们必须将算法向基本情况的状态改变。状态的改变意味着该算法正在使用的一些数据被修改。通常，表示问题的数据在某种程度上变小。在 listsum 算法中，我们的主要数据结构是一个列表，因此我们必须将我们的状态转换工作集中在列表上。因为基本情况是长度 1 的列表，所以朝向基本情况的自然进展是缩短列表。在 Activecode 2 第五行，我们调用 listsum 生成一个较短的列表。

最后的法则是算法必须调用自身。这是递归的定义。递归对于许多新手程序员来说是一个混乱的概念。作为一个新手程序员，你已经知道函数是有益的，因为你可以将一个大问题分解成较小的问题。较小的问题可以通过编写一个函数来解决。我们用一个函数解决问题，但该函数通过调用自己解决问题！该逻辑不是循环;递归的逻辑是通过将问题分解成更小和更容易的问题来解决的优雅表达。

在本章的剩余部分，我们将讨论更多递归的例子。在每种情况下，我们将集中于使用递归的三个定律来设计问题的解决方案。