《计算思维与Ｃ语言概述》-第七章

７.１递归

递归(ｒｅｃｕｒｓｉｏｎ)是计算科学领域的一种重要的思维模式，是一种问题求解的方法。例如，数学公式ｎ!＝１×２×···×ｎ的计算可以取ｎ－１次乘法的结果，也可以采用另一种思维方法———ｎ!＝ｎ(ｎ－１)!。也就是说，给定ｎ，则ｎ!可由(ｎ－１)!求出，(ｎ－１)!可由(ｎ－２)!求出，···，２!可由１!求出。而１!＝１已知，那么２!可求得，

从而３!可求得，

依次类推，

ｎ!可求得。

这种思维方式便是一种递归。

递归思维将复杂的计算简化为简单计算的不断重复，是最重要的计算思维。在Ｃ/Ｃ＋＋语言中，递归的实现是采用函数的自我调用来实现。函数直接

(或间接)调用自己就称为函数的递归调用，这种函数就称为递归函数。递归函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，

就一层一层地由里到外返回。

调用自身的过程又称为“递推”，由里到外返回的过程又称为“回归”，所以递归过程可以分为“递推”和“回归”两个阶段。下一页返回７.１递归

本节以一个简单示例为基点，阐述应用递归的程序设计过程。【例７－１】用递归函数编写计算阶乘ｎ!的函数ｆａｃｔｏｒｉａｌ。【分析】阶乘ｎ!的计算公式如下:根据上面阶乘的计算公式可以发现，阶乘的计算公式是一个递归计算公式。为了计算ｎ!，

需要调用计算阶乘的函数ｆａｃｔｏｒｉａｌ(ｎ)，

它因要计算(ｎ－１)!，

而调用ｆａｃｔｏｒｉａｌ(ｎ－１)，于是形成递归调用。

这个过程一直持续到１!为止。

在求得１!＝１以后，

逐层返回，

最后求得ｎ!。上一页下一页返回７.１递归

算法的伪代码如下:(１)输入一个自然数，

存入变量ｎ；(２)递归调用函数ｆａｃｔｏｒｉａｌ；(３)输出ｎ!的值；上一页下一页返回７.１递归

７.１.１

递归的思想递归是程序设计中的一种常见方法。采用递归方法编写程序可以使程序更加简洁、清晰、

容易理解。

阶乘问题是一个经典的数学递归问题。

为了得到ｎ!，

操作步骤如下(注意参数的变化):(１)第１次调用函数ｆａｃｔｏｒｉａｌ(ｎ)。

根据公式可知:ｎ!＝ｎ×(ｎ－１)!。所以，

需要知道(ｎ－１)!的数值，

那么就需要第２次调用函数ｆａｃｔｏｒｉａｌ。(２)第２次调用函数ｆａｃｔｏｒｉａｌ(ｎ－１)。

根据公式可知:(ｎ－１)!＝(ｎ－１)×(ｎ－２)!。所以，需要知道(ｎ－２)!的数值，

那么就需要第３次调用函数ｆａｃｔｏｒｉａｌ。(３)第３次调用函数ｆａｃｔｏｒｉａｌ(ｎ－２)。

根据公式可知:(ｎ－２)!＝(ｎ－２)×(ｎ－３)!。所以，需要知道(ｎ－３)!的数值，

那么就需要第４次调用函数ｆａｃｔｏｒｉａｌ。上一页下一页返回７.１递归

直到调用函数ｆａｃｔｏｒｉａｌ(２)，

都可采用同样的方法进行处理，

２!＝２×１!。

根据公式可知:１!＝１。

因此，

问题最终可以求解。可以看出，每次面对的问题在本质上是同一个问题，只是问题的规模不同。上面的解决方法体现了递归的思想，将复杂问题分解为规模较小的子问题，

且子问题和原问题本质上是相同的问题。在将子问题求解后，原问题也将求解。接下来，

以求解５!为例，

说明递归的递推过程和回归过程。上一页下一页返回７.１递归

７.１.２

递归的递推求解５!的递推过程如下:(１)求解５!，

即调用ｆａｃｔｏｒｉａｌ(５)。

当进入ｆａｃｔｏｒｉａｌ()函数体后，

由于形参ｎ的值为５，不等于１，

所以执行ｆａｃｔｏｒｉａｌ(ｎ－１)∗ｎ，

即执行ｆａｃｔｏｒｉａｌ(４)∗５。

为了求得这个表达式的结果，

必须先调用ｆａｃｔｏｒｉａｌ(４)，

并暂停其他操作。

换言之，

在得到ｆａｃｔｏｒｉａｌ(４)的结果之前，不能进行其他操作。(２)调用ｆａｃｔｏｒｉａｌ(４)时，

实参为４，

形参ｎ

也为４，

不等于１，

因此将继续执行ｆａｃｔｏｒｉａｌ(ｎ－１)∗ｎ，

即执行ｆａｃｔｏｒｉａｌ(３)∗４。

为了求得这个表达式的结果，

必须先调用ｆａｃｔｏ-ｒｉａｌ(３)。上一页下一页返回７.１递归

(３)调用ｆａｃｔｏｒｉａｌ(３)时，

实参为３，

形参ｎ

也为３，

不等于１，

因此将继续执行ｆａｃｔｏｒｉａｌ(ｎ－１)∗ｎ，

也即执行ｆａｃｔｏｒｉａｌ(２)∗３。

为了求得这个表达式的结果，

又必须先调用ｆａｃｔｏｒｉａｌ(２)。(４)调用ｆａｃｔｏｒｉａｌ(２)时，

实参为２，

形参ｎ也为２，

不等于１，

因此将继续执行ｆａｃｔｏｒｉａｌ(ｎ－１)∗ｎ，

即执行ｆａｃｔｏｒｉａｌ(１)∗２。

为了求得这个表达式的结果，

必须先调用ｆａｃｔｏ-ｒｉａｌ(１)。(５)在进行４次调用后，

实参的值为１，

因此将调用ｆａｃｔｏｒｉａｌ(１)。

此时，

能够直接得到常量为１的值，

并把结果返回，

不需要再次调用ｆａｃｔｏｒｉａｌ()函数，

递归结束。表７－１列出了在递归调用过程中逐层进入的递推过程。上一页下一页返回７.１递归

７.１.３递归的回归当递归进入最内层时，就结束递归，开始逐层退出，即逐层执行ｒｅｔｕｒｎ语句，这就是递归的回归过程。

求解５!的回归过程如下:(１)当ｎ的值为１时，

达到最内层，

此时ｒｅｔｕｒｎ的结果为１，

即ｆａｃｔｏｒｉａｌ(１)的调用结果为１。(２)有了ｆａｃｔｏｒｉａｌ(１)的结果，

就可以返回上一层，

计算ｆａｃｔｏｒｉａｌ(１)∗２的值。

此时，得到的值为２，

ｒｅｔｕｒｎ的结果也为２，

即ｆａｃｔｏｒｉａｌ(２)的调用结果为２。(３)有了ｆａｃｔｏｒｉａｌ(２)的结果，

就可以返回上一层，

计算ｆａｃｔｏｒｉａｌ(２)∗３的值。

此时，得到的值为６，

ｒｅｔｕｒｎ的结果也为６，

即ｆａｃｔｏｒｉａｌ(３)的调用结果为６。上一页下一页返回７.１递归

(４)有了ｆａｃｔｏｒｉａｌ(３)的结果，

就可以返回上一层，

计算ｆａｃｔｏｒｉａｌ(３)∗４的值。

此时，得到的值为２４，

ｒｅｔｕｒｎ的结果也为２４，

即ｆａｃｔｏｒｉａｌ(４)的调用结果为２４。(５)有了ｆａｃｔｏｒｉａｌ(４)的结果，

就可以返回上一层，

计算ｆａｃｔｏｒｉａｌ(４)∗５的值。

此时，得到的值为１２０，

ｒｅｔｕｒｎ的结果也为１２０，

即ｆａｃｔｏｒｉａｌ(５)的调用结果为１２０。

这样就得到了５!的值。表７－２列出了在递归调用过程中逐层退出的回归过程。上一页下一页返回７.１递归

７.１.４递归的条件每一个递归函数都应该只进行有限次递归调用，否则就会进入死胡同，

永远也不能退出，这样的程序是没有意义的。要想让递归函数逐层进入再逐层退出，需要解决以下两方面的问题:(１)存在限制条件，

当符合该条件时，

递归便不再继续。

对于函数ｆａｃｔｏｒｉａｌ，

当形参ｎ等于１时，递归就结束。这种限制条件就是递归结束条件，称为递归出口。(２)每次递归调用后，

越来越接近该限制条件。

对于函数ｆａｃｔｏｒｉａｌ，

每次递归调用的实参为ｎ－１，这会使形参ｎ的值逐渐减小，越来越趋近于１。上一页下一页返回７.１递归

７.１.５

递归的实现经过上面递归调用的分析，例７－１的程序代码如下:上一页下一页返回７.１递归

上一页下一页返回７.１递归

【练习】(１)用递归方法求１~１００的和，

即１＋２＋３＋４＋···＋１００。提示:递归求和公式为(２)用递归方法求１~１００的连乘积，

即１×２×３×４×···×１００。提示:递归求连乘积公式为(３)从１，２，３，···，ｎ中取出ｍ个数，一共有多少种选择方案?提示:计算从ｎ个数中取ｍ个数的组合数的公式为上一页返回７.２迭代与递归

在计算机编程实现中，

常常有两种编程思想:迭代(ｉｔｅｒａｔｅ)；

递归(ｒｅｃｕｒｓｉｏｎ)。

从概念上讲，递归是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值的编程思想。简而言之，递归将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已知答案的最小问题为止，然后逐级返回，从而得到大问题的解；而迭代则从已知值出发，通过递推式，不断更新变量新值，直到能够解决问题为止。下面以斐波那契数列的求解为例，介绍这两种典型编程思想的实现，并分析二者的区别与联系。下一页返回７.２迭代与递归

【例７－２】斐波那契数列(又称为黄金分割数列，

通常记做Ｆｉｂｏｎａｃｃｉ)指的是这样一个数列:１，１，２，３，５，８，１３，２１，···这个数列从第３项开始，每一项都等于前两项之和。该数列刚好和一个有趣的兔子问题相关。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么若干个月以后的兔子对数为:１，１，２，３，５，８，１３，３１，···【分析】如果在数列的前面加上数字“０”，那么从第２项开始，每一项都是该项前两项的数字之和。

数列的通项表达式Ｆ(ｎ)如下:上一页下一页返回７.２迭代与递归

７.２.１

递归实现可以采用递归的编程方式求解例７－２的问题，方法是定义一个函数Ｆｉｂ，返回数列第ｎ项的值。将规模为ｎ的问题分解为更小规模的问题，即规模为ｎ－１的问题与规模为ｎ－２的问题，

一直分解到规模为０和规模为１的问题。

数列的通项表达式Ｆｉｂ(ｎ)如下所示:例７－２递归函数的伪代码如下:(１)如果函数形参是０，

则函数返回０，

并回归上一层；(２)如果函数形参是１，

则函数返回１，

并回归上一层；(３)如果函数形参大于１，

则继续递归调用函数。上一页下一页返回７.２迭代与递归

将例７－２采用递归求解的函数Ｆｉｂ的代码如下:上一页下一页返回７.２迭代与递归

７.２.２

迭代实现例７－２也可以采用迭代的方式求解。同样，需要定义一个函数Ｆｉｂ，但不将问题分解，而是直接利用已知的变量值，根据递推公式不断演进。由例７－２的递推公式可知，已知两个初值(即数列第０项的值和数列第１项的值)，那么根据递推公式，就可以得到第２项的值，，得到第ｎ项的值。算法的伪代码如下:(１)定义两个变量ｆ０和ｆ１，

初值分别为０和１；(２)如果函数形参ｎ是０，

则函数返回０；(３)如果函数形参ｎ是１，

则函数返回１；(４)循环变量ｉ初始化为２，

当循环变量ｉ≤ｎ时，(４.１)计算数列下一项的值，

ｆ＝ｆ０＋ｆ１；(４.２)更新变量，

ｆ０＝ｆ１，

ｆ１＝ｆ；(４３)ｉ＋＋；(５)函数返回ｆ的值。上一页下一页返回７.２迭代与递归

将例７－２采用迭代求解的函数Ｆｉｂ代码如下:上一页下一页返回７.２迭代与递归

上一页下一页返回７.２迭代与递归

【练习】(１)改写上述迭代算法，

将一维数组作为Ｆｉｂ函数的形参，

把前ｎ项斐波那契数列存入数组，并编写ｍａｉｎ函数，输出斐波那契数列前１００项的数值，输出方式为每行１０项。(２)将７１５节练习１和练习２的递归程序改写为迭代程序。(３)求ｘ平方根近似值的迭代公式为ｘｎ

＋

１＝(ｘｎ＋ｘ/ｘｎ

)/２。

当ｎ为１时，

ｘ１为ｘ，

迭代一次求得的平方根近似值为ｘ２；ｎ为２时，求得的近似值为ｘ３，依次类推。输入正整数ｘ和整数ｎ(ｎ≥０，

且ｘ和ｎ都不会出现溢出情况)。

求利用上述公式，

求ｘ迭代ｎ次后的平方根近似值，保留计算结果小数点后５位有效数字。例如，输入１６和４，

则输出４００２２６。上一页下一页返回７.２迭代与递归

７.２.３

递归与迭代的关系递归，实际上就是不断地深层调用函数，直到函数有返回值才会逐层返回。因此，

递归涉及运行时的堆栈开销(参数必须压入堆栈保存，直到该层函数调用返回为止)，有可能导致堆栈溢出的错误。但是，递归编程所体现的思想正是人们追求简洁、将问题交给计算机，以及将大问题分解为相同小问题从而解决大问题的动机。迭代在大部分时候需要人为地对问题进行剖析，

将问题转变为一次次的递推来逼近答案。迭代不像递归一样对堆栈有一定要求，一旦问题剖析完毕，就可以很容易地通过循环加以实现。在理论上，递归和迭代在时间复杂度方面是等价的(暂不考虑函数调用开销和函数调用产生的堆栈开销)，但实际上，递归的效率比迭代低。既然递归没有任何优势，

那么是不是就没有使用递归的必要了?递归的存在有何意义呢?上一页下一页返回７.２迭代与递归

从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都比较高。但是，就算法结构而言，递归声明的结构并不总能转换为迭代结构；就实际而言，所有的迭代都可以转换为递归，但递归不一定可以转换为迭代。迭代虽然效率高，运行时间只因循环次数增加而增加，没什么额外开销，空间上也没有什么增加，但其代码不易理解，

在编写复杂问题时，算法实现较为困难。上一页返回７.３实训与实训指导

实训１

走台阶有个人刚刚看完电影«第３９级台阶»，离开电影院时，他数了数礼堂前的台阶数，恰好是３９级!站在台阶前，他想到一个问题:如果我每一步只能迈上１个或２个台阶，先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要走偶数步。那么，上完３９级台阶，有多少种不同的上法呢?１实训分析为了统计走完３９级台阶的方法，设结果变量ｒｅｓｕｌｔ表示上台阶的方法数，初始值是０。由于每走到一级台阶，都需要统计步数，所以设变量ｎｕｍ表示台阶，ｓｔｅｐ表示走到ｎｕｍ级台阶的步数。题目中说明每一步只能迈上１个或２个台阶，所以第ｓｔｅｐ＋１步有可能到达ｎｕｍ＋１级台阶，也有可能到达ｎｕｍ＋２级台阶。第ｓｔｅｐ＋２步也是同样的情况，依次类推。这里也就是程序的递归。那么当ｎｕｍ＝３９时，表示此时走完３９级台阶。下一页返回７.３实训与实训指导

由于题目中要求先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要走偶数步，所以当ｎｕｍ＝３９时，还需要判断当前的步数是否为偶数步，即“ｓｔｅｐ％２＝＝０”是否成立。如果满足偶数步，则表示一种方案成立，即ｒｅｓｕｌｔ＋＋；如果不满足偶数步，表示这种走法不符合要求，舍弃。算法的伪代码如下:(１)设置递归的初始条件，

第ｎｕｍ＝０级台阶，

共走ｓｔｅｐ＝０步；(２)处理递归的下一步，

对于ｓｔｅｐ＋１级台阶，

ｎｕｍ－２或者ｎｕｍ－１，

判断递归是否结束；(３)输出结果。上一页下一页返回７.３实训与实训指导

程序的代码如下：上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

２实训练习编写程序递归实现某个自然数ｎ的ｋ次幂。提示:递归公式为上一页下一页返回７.３实训与实训指导

实训２

换汽水已知１元可以买１瓶汽水，３个瓶盖可以换１瓶汽水，２个空瓶也可以换１瓶汽水。那么，ｎ元总共可以买到多少瓶汽水?１实训分析不妨设变量ｍｏｎｅｙ、ｗａｔｅｒ分别表示钱的金额数和当前的汽水数量。题目中说明１元可以买１瓶汽水，所以汽水的最初数量等于钱的金额大小，即ｗａｔｅｒ＝ｍｏｎｅｙ。另外，设变量ｃａｐ、ｂｏｔｔｌｅ分别表示当前的瓶盖数量和空瓶数量。由题目可知，３个瓶盖可以换１瓶汽水，２个空瓶也可以换１瓶汽水，所以此时瓶盖和空瓶可以兑换的汽水数量分别为ｃａｐ/３、ｂｏｔｔｌｅ/２。因此，汽水的数量由两部分组成，即之前的汽水数量和兑换的汽水数量。上一页下一页返回７.３实训与实训指导

兑换汽水后，

瓶盖和空瓶的数量分别是ｃａｐ％３、ｂｏｔｔｌｅ％２，可以用来兑换的汽水数量是ｃａｐ/３＋ｂｏｔｔｌｅ/２。如此便可以进行下一次兑换，这就是该题的递归部分。直到可兑换的汽水数量等于０时，递归结束。算法的伪代码如下:(１)根据１元买１瓶汽水的原则，

可知初始汽水的数量ｗａｔｅｒ＝ｍｏｎｅｙ；(２)初始化递归的条件，

可以用来兑换的汽水数量:ｗａｔｅｒ＝ｍｏｎｅｙ，

ｃａｐ＝０，

ｂｏｔｔｌｅ＝０；(３)兑换后，

更新ｃａｐ、

ｂｏｔｔｌｅ的数值，

并判断是否有下一次兑换的可能性。

如果还可以兑换，则继续递归；否则，退出递归。上一页下一页返回７.３实训与实训指导

程序的代码如下：上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

２实训练习编写程序，利用递归公式求函数值:上一页下一页返回７.３实训与实训指导

实训３

排列数从ｎ个不同元素中任取ｍ(ｍ≤ｎ)个元素，

按照一定的顺序排列起来。

当ｍ＝ｎ时，

所有的排列情况称为全排列。例如，１、２、３三个元素的全排列如下:１，２，３１，３，２２，１，３２，３，１３，１，２３，２，１上一页下一页返回７.３实训与实训指导

１实训分析常用的全排列方法有递归算法和非递归算法。其中，递归算法有四种:字典序法、递增进位制数法、递减进位制数法和邻位对换法。字典序法的排列规则:对给定的字符集中的字符规定一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。

例如，

对于字符集{１，２，３}，

要求将较小的数字排序较先，

这样按字典序法生成的全排列是:１２３，１３２，２１３，２３１，３１２，３２１。

递归算法由函数Ｐｅｒｍ(ｉｎｔｌｉｓｔ[]，ｉｎｔｋ，ｉｎｔｍ)实现，将ｌｉｓｔ的前ｋ个元素作为前缀、剩下的ｍ－ｋ个元素进行全排列而得到排列。其想法是将第ｋ个元素与后面的每个元素进行交换，求出其全排列。上一页下一页返回７.３实训与实训指导

算法的伪代码如下:(１)读入参与全排列的数据个数以及具体的数值；(２)从左向右逐个与后面的元素进行交换；(３)递归上述过程，

直到得到ｎ个数，

得到一个全排列；(４)为了下一个全排列，

需要把刚才发生交换的两个数值恢复原状态。

然后，

继续２和３，寻找下一种全排列。上一页下一页返回７.３实训与实训指导

程序的代码如下：上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

上一页下一页返回７.３实训与实训指导

２实训练习Ａ~Ｉ代表１~９的数字，不同的字母代表不同的数字。字母Ａ~Ｉ组成了下面的算式:某些数字的排列刚好使该式成立。例如，６＋８/３＋９５２/７１４就是一种解法，５＋３/１＋９７２/４８６是另一种解法。这个算式一共有多少种解法?提示:考虑１~９的每种全排列能否使该式成立即可。上一页下一页返回７.３实训与实训指导

实训４

汉诺塔汉诺塔(ＨａｎｏｉＴｏｗｅｒ)又称河内塔，

已知有三根柱子，

在一根柱子上从下往上按照大小顺序摞着６４个圆盘。现在需要把圆盘按大小顺序重新摆放在另一根柱子上。规定:任何时候，在小圆盘上都不能摆放大圆盘，且在三根柱子之间一次只能移动一个圆盘。如果将三根柱子分别命名为Ａ、Ｂ、Ｃ，Ａ柱子上有ｎ片黄金圆盘，应该如何操作才能实现该任务?编写程序输出圆盘移动的操作步骤。要求从键盘接收圆盘的数量。上一页下一页返回７.３实训与实训指导

１实训分析对于这样一个问题，我们很难直接给出圆盘移动的顺序。但是，可以先观察圆盘数量较少时的规律，进而解决这个问题。假设Ａ柱子上的ｎ个圆盘从上至下的编号依次为１、２、···、ｎ，规定将圆盘从Ａ柱子直接移动到Ｃ柱子上的过程记为Ａ→Ｃ，则:(１)当ｎ＝１时，第１次移动:１号圆盘Ａ→Ｃ。(２)当ｎ＝２时，第１次移动:１号圆盘Ａ→Ｂ；第２次移动:２号圆盘Ａ→Ｃ；第３次移动:１号圆盘Ｂ→Ｃ。可以看出，第１次移动将２号圆盘上的１号圆盘从Ａ柱子移到Ｂ柱子上。第２次移动将２号圆盘从Ａ柱子移到Ｃ柱子上。第３次移动除将２号圆盘外的１号圆盘从Ｂ柱子移动到Ｃ柱子上。上一