1.3.1 什么是递归_计算机数学：算法基础线性代数与图论-QQ阅读男生历史网

上QQ阅读APP看书，第一时间看更新

1.3.1 什么是递归

我们知道，用解析法表示函数常有：显函数形式y= f（x）、隐函数形式 f（x,y）=0、参数方程形式（t 为参数）。在学习数列时，通项公式可确定一个数列，递推公式也可确定数列。如斐波那契数列（1,1,2,3,5,8,13,21,…）是用a1=1、a2=1以及当n＞2时， an=an−1+an−2定义的数列。函数也有递归定义形式，如 f （n）=2f （n−1）+1。计算机术语中，实现某些功能的程序段也称为函数。各种计算机高级语言都有函数的嵌套调用和递归调用，什么是递归呢？

1.递归

自己调用自己，称为递归。自己调用自己的函数，称为递归函数。递归函数包括直接递归和间接递归。直接递归是指函数F的代码中直接包含了调用F的语句，而间接递归是指函数F调用了函数G,G又调用了H，如此进行下去，直到F又被调用。

如求n的阶乘运算，定义：n!=（n−1）!×n。定义中n！与（n−1）！的算法是相同的，本质上它们是同一函数，求n!，先要求（n−1）!，所以，阶乘函数体现了自己调用自己。

例1.10 由初值y 0 =1.41和递推关系yn =10 yn−1−1（n=1, 2, 3, 4, …）确定的数列（函数），设f （n）=yn，则yn-1=f （n−1），本质上函数f （n）与f （n−1）是相同的。所以，这个函数的递归定义可表示为

其中，f（n）=10 f（n−1）−1为递归关系，f （0）=1.41为递归的初始条件。递归定义中这两个条件缺一不可。如果缺少最初的项，即使已知递归关系，也不能求出递归关系中包含的各项的值。类似的，由初值 x1=1和递推关系确定的函数的递归定义是

一般的，递归函数包含初始条件和递归表达式，可以用如下形式表达。

与递归函数类似的说法，还有：

递归调用：在函数内部发出调用自身的操作。

递归算法：直接或者间接地调用自身的算法。

递归方法：通过函数或过程调用自身将问题转换为本质相同但规模较小的子问题的方法。

2.递归算法的基本思想与构成

递归方法实际上体现了“以此类推”“用同样的步骤重复”这样的思想，是算法和程序设计中的一种重要技术。如在“s（n）=s（n−1）+n=1+2+…+n”这个语句中，我们求s（n）值的时候，必须先调用s（n−1）；而要得到s（n−1），又必须调用s（n−2）；同样，要求s（n−2）又要调用s（n−3）。依此类推，一直要递推到s（2）=s（1）+2，已知s（1）=1，然后代入求得s（2），从而得到s（3），这样一直可以得到s（n）。

从这个递归调用过程可以看到，递归算法需要具备的两个重要条件。

（1）自身调用的语句，如s（n）=s（n−1）+n；

（2）递归终止条件（即已解决的基础问题），如s（1）=1。

3.递归的逻辑过程

计算机执行递归算法程序时，总是在进行“调用”与“返回”，程序运行过程是先“调用”后“返回”。

调用过程：

每一次调用自身，参数值逐渐变小，直到调用已知条件，即递归终止条件，调用结束。

如设f（n）=n!，求5!，分别调用f（5）,f（4）,f（3）,f（2）,f（1）,f（5）=f（4）×5,f（4）=f（3）×4,f（3）=f（2）× 3,f（2）=f（1）×2,f（1）=1。

返回过程：

从已知条件出发，按“调用”的逆过程，逐步求值返回。从 f（1）出发，返回到 f（2）,f（2）的值返回到 f（3）,f（3）的值返回到 f（4）,f（4）的值返回到 f（5），求得结果。计算机高级语言中有返回语句（return）来指示如何返回（在哪里调用了就返回到调用地点）。

计算机执行递归算法程序时如图1.11所示。

4.递归算法的优缺点

递归算法的优点：可以用简单的程序来解决某些复杂的计算问题，使源程序非常简洁。有一些算法本质上只有递归算法。

递归算法的缺点：运算量较大，消耗较多的内存和运行时间，且效率不高。

例1.11 递归定义的图形——Koch曲线。

Koch曲线最初形式是一条线段，由G0表示，如图1.12所示。

图1.11

图1.12

将线段3等分，把中间部分用两条等长的线段代替，被代替的线段与两条新增线段组成一个等边三角形，得到G1，如图1.13所示。

将G1中的每一段线段按上述方法修改，得到G2，如图1.14所示。

将G2中的每一段线段按上述方法修改，如图1.15所示。如此一直不断修改下去，最后得到的图形称为Koch曲线。

Koch曲线是以一条线段为基本图形元素，用相同的规则对每一条线段进行修改，分割成更小的部分而生成的有趣图形。生成Koch曲线的递归算法需要考虑：

（1）由G0得到G1产生了5个点P1、P2、P3、P4、P5（见图1.16），其中P1、P5是最初线段的2个端点，P2、P3、P4是修改图形依次插入的3个端点。P2位于P1右侧线段的处，P4位于P1右侧线段的处，P3由P4绕P2逆时针旋转得到。所以，由线段两个端点坐标可表示插入的三个点的坐标。旋转矩阵。每次图形迭代，只需确定和修改P1、P5的坐标。