python学习5--递归（recursion）

比眉伴天荒 2022-02-01 07:55 177阅读 0赞

在这第五次课程中，我们将首先讨论已经写过的函数，  
特别是如何以将它们看作迭代计算处理。  
**迭代计算抓住了计算的核心**，  
即循环内的每次迭代都会更新一系列的状态变量。  
基于此，我们接下来将会讨论一个非比寻常的概念——**递归**。  
在递归中，我们可以将计算简化为相同问题更加简单的版本，运用这一概念方便快速地开展计算过程。

*  我们还将展示递归这一概念是如何建立在概念归纳的基础之上的。
 *  而且我们会特地运用这一点来解释为什么递归算法这么有用。
 *  此外，我们会运用这一概念（递归）引出设计递归算法的通用原理。
 *  为此，我们将展示一些经典又有趣的递归算法，特别是我们称之为“分而治之”的方法。

ERIC GRIMSON: 我们已经把函数添加进了  
工具库，我们将会看到这有多么强大，  
能够帮助我们以计算思维  
解决问题。  
如前所述，函数赋予我们抽象的能力，  
能够捕捉计算过程，并把它包装成  
原语，因此，我们可以将函数  
看作黑盒。  
你可以压缩细节并仅仅使用合同。  
合同中指明，如果你提供给的东西满足特定约束条件，  
该函数就可以返回给你  
满足特定需求的答案。  
这太好了。  
但是，即便是函数，也有不同的风格。  
函数真正的长处在于  
以各种不同的方式处理计算问题。  
我想在这一部分花一些时间  
来探讨一下这件事。  
让我们从目前已经了解到的知识开始。  
事实上，我们一直使用循环结构，将其作为  
一种构建算法的方式。  
而那些循环结构，比如当型循环，for循环，  
很自然地引出了我们所说的  
迭代算法。  
他们在循环中不断迭代，一遍遍地  
执行相同的计算过程，其中只有微小的变化。  
特别是我们可以将一个迭代算法  
看作在一系列变量内捕捉计算过程的手段，  
其中的变量就是我们所谓的“状态变量”。  
这些变量描述了  
计算状态。  
循环的每一次迭代，  
都会更新或改变变量的数值。  
让我们来看一个例子。  
这就是一个简单的示例。  
试想我们要做一次乘法，  
方法是连续相加。  
这样，我们的电脑就仅需处理加法运算。  
它并不需要使用乘法。  
我知道那样做很笨，  
但是这样处理起来十分方便。  
如果你想要这么做，也就是通过连续加的方法进行乘法运算，  
那么一个简单的方法就是  
如果我们要计算 a x b，  
我们仅需让 a 自我相加 b 次。  
从迭代的角度来看，这意味着什么呢？  
表面上，我们可以说这个计算过程只  
涉及两个变量。  
一个是迭代次数。  
我已经循环了多少次？  
这个数字，不妨称其为 i，  
它应该是起始于b。  
我们所需的第二个变量就是状态变量，  
它计算  
我们已经进行了多少次加法。  
现在的结果又是怎样。  
我们叫它结果。  
所以它就是计算当前的状态，  
由0开始。  
请注意，每个状态变量都有一个  
初始化的过程。  
我们从某处起始，  
然后，我们将该计算看作  
状态变量的迭代或更新过程。  
本案例中，那些更新规则  
就变成了这样：每个迭代，我的迭代次数i就会减1，  
而计算所求的结果  
会选取当前结果的数值  
加上a的数值，成为  
状态变量的新值。  
状态变量有一个特点：  
如果计算停在任意一点，  
它们可以准确地告诉我自己的所在位置。  
它们还有一个特点，  
它们不止可以被初始化，同时至少会有1个状态变量  
告诉我何时可以终止循环。  
此例中，我会在迭代的重复计数  
下降为0时停止。  
我知道所有需要做的事情都已完成。  
我们已经看到了诸如此类的案例，  
我们也很好地掌握了迭代的概念。  
如果我们把该案例引入代码中，事实上，我们会看见  
这段基于此的代码非常棒。  
我们将一个状态变量初始化。  
在这个案例中，我们将利用输入的变量，  
并将它作为另一个状态变量来使用。  
它在传入的时候就会设置初始值。  
然后循环就会更新。  
这就是状态变量的更新过程。  
请允许我简单评论一下此格式，  
这是由于我们以前从未用到过它。  
它的意思就是让结果  
与原结果加 a相绑定。  
而这句的意思是，让 b 等于 b 减 1。  
这是一种简单的速记方法，来进行  
这种计算。  
当然了，当我完成时，  
我会返回计算结果。  
之前我们已经看过这类例子了。  
而且你可以看到，迭代是一种极佳的  
思维方式。  
事实上，循环会捕捉到每轮循环中  
状态变量的变化情况。  
如果我们尝试一下的话，  
当然可以转向Python。  
这里就是我对 iterMul（迭代乘法）的定义。  
如果我用IDLE环境加载它的话，  
那么我当然可以这么说，  
告诉我3和5迭代相乘（结果），然后它就照着做了。  
我甚至可以做一些更加奇特的事情，比如这样。  
它的速度非常快。  
我们还未展示出该循环中间的过程，  
但是你已经看到足够多的例子，帮助你了解它，  
这事实上就是在递减变量 b的同时，  
累计结果变量，  
然后输出数值。  
非常好。  
下载字幕  
.srt