程序设计基础_13521005.pdf,参考本书P91页~P97页的内容(已包含无页码页22页),请你参考这本书的内容,尽量举相似的例子,在linux系统下的C++环境下,写一篇第四章知识总结和教程。用浏览器查看渲染情况。
递归及其实现:知识总结与教程
本页依据教材 P91-P97 的内容编写(实际对应教材第 6 章 6.3 递归及其实现、6.4 知识拓展、6.5 思考与实训、6.6 小结、6.7 知识巩固)。例题与教材保持同一类型,只把数字稍作替换;所有代码均在 Linux + g++ 环境下可直接编译运行。
一、递归的两个必备要素
教材用求 n! 这一个任务贯穿全节。
解题思路(教材要点):当 n ≥ 0 时,求 n! 的问题可以转化为求 n×(n-1)! 的新问题,而求 (n-1)! 的解法与原来求 n! 的解法相同,只是运算对象由 n 变成了 n-1;每转化一次新问题,运算对象就递减 1,直到递减至 0 时阶乘的值为 1,递归结束。
写成数学形式:
┌ 1 当 n = 0 时
n! = │
└ n × (n-1)! 当 n > 0 时
由此得出写递归函数的两个必备要素:
- 递归关系(递推公式):n! = n × (n-1)!,当 n > 0
- 递归边界(终止条件):0! = 1,即 n = 0 时不再调用自己
缺一不可:没有边界就会无限递归;没有递归关系就无法把大问题化小。
二、教材的分析工具:与或节点图
教材为了把递归讲得直观,定义了两个节点:
- 或节点:用空心圆 ○ 表示。图中 A 为或节点时,按条件 Z 的真假在 B、C 中取一个值,即 A = (Z 为真 ? B : C)。如果取值多于两种,就按条件 Z1、Z2、…、Zn 在 B、C、…、G 中取一个。
- 与节点:用实心圆 ● 表示,相关联的节点之间用弧线连起来。A 为与节点时,A 的最终取值是最后一个节点(最右边那个)的值;但为了求得它的值,必须先求出左边节点的值——也就是“先求左边的点,才能求最右边的点的值”。与节点也可能关联多个节点。
| 对比项 | 或节点 ○ | 与节点 ● |
|---|---|---|
| 图形约定 | 空心圆 | 实心圆,关联分支之间画弧线 |
| 取值方式 | 按条件在多个分支中选一个 | 关联的节点都要算,取最右边节点之值 |
| 求值顺序 | 由条件决定 | 从左到右,有先后次序 |
| 在 n! 中的对应 | fact(n) 这个整体 | “先求 fact(n-1),再乘 n” 这一步计算 |
相似例子:4! 的与或节点图(教材用 3! 举例,此处换成 4!,结构与教材图 6.8、图 6.10 完全一致):
fact(4) ○ 或节点
├── 条件 n = 1 ──> 1 直接可解节点(值为 1)
└── 条件 n > 1 ──> ● 与节点
├── D: fact(3) 先求 D
└── E: 4 * fact(3) 后求 E,A 的值 = E 的值
展开与回代(教材的“剥白菜”比喻:从外向里一层层剥到菜心,再从里向外推回去):
展开(调用) 回代(返回) fact(4) = 4 * fact(3) fact(1) = 1 fact(3) = 3 * fact(2) fact(2) = 2 * 1 = 2 fact(2) = 2 * fact(1) fact(3) = 3 * 2 = 6 fact(1) = 1 <-- 递归边界 fact(4) = 4 * 6 = 24
对照教材图 6.11(调用和返回)、图 6.12 与图 6.13(fact(3) 的两个程序框图)可以看出:“内层”与“外层”结构完全相同,它们之间“你中有我,我中有你”,这正是递归的结构特征。
三、递归与递推的比较
仍以求阶乘为例,教材的递推写法是“从已知的初始条件出发,逐次去求所需要的阶乘值”:
fact(1) = 1 fact(2) = 2 * fact(1) = 2 fact(3) = 3 * fact(2) = 6
| 对比项 | 递推 | 递归 |
|---|---|---|
| 出发点 | 已知的初始条件 | 求解的目标 |
| 方向 | 从“菜心”推到“外层” | 从目标逐层调用到边界,再逐层返回 |
| 是否容易写 | 很多实际问题找不到显见的递推关系 | 写清递归关系 + 边界即可 |
| 可读性 | 一般 | 简明扼要、逻辑性强、接近人的思维方式 |
| 效率 | 较高 | 较低(原因是增加时间开销) |
教材结论:许多相当复杂、或难以下手的问题,如果能够使用递归方法,就能化难为易。
四、递归为什么"贵"
教材原文要点:函数自己调用自己时,系统会自动把函数中当前的变量和形参暂时保存起来,在新一轮调用过程中,系统又会为该次调用用到的变量和形参另外开辟存储单元。因此:
- 递归调用的层次越多,同名变量占用的存储单元也就越多;
- 本次调用的函数运行结束时,系统才释放本次调用占用的存储单元,执行流程返回到上一层的调用点,同时取回当初进入该层时变量和形参的数据;
- 这样做势必增加时间开销。
实践建议:能找到显见递推关系就先递推;“递归层次深 + 重复子问题多”的情形(如朴素的斐波那契递归)要改造(记忆化或改递推)。
五、任务 6.5:用递归算法求 n!(教材程序 6_8.cpp)
把教材程序去掉注释头和逐行注释后,逻辑如下:
#include <iostream> using namespace std; float fact(int n) // 定义 fact() 函数,返回值为实型 { float s; // 定义实型变量 if (n == 0) return 1; // 递归边界:n = 0 时返回 1 else { s = n * fact(n - 1); // 递归关系:调用 fact(n-1),乘以 n 后赋给 s return s; // 返回值 s } } int main() { int n; float y; cout << "您要查询第几项? "; cin >> n; if (n < 0) cout << "您的输入不正确" << endl; else { y = fact(n); // 调用 fact(),返回值赋给 y cout << n << "!=" << y << endl; } return 0; }
Linux 下的编译与运行(务必上机跑一遍,弄清递归是如何进行的):
g++ -Wall -o fact fact.cpp ./fact 您要查询第几项? 5 5!=120
两点自己动手的改进:
- 教材把返回值定为 float,float 只有约 7 位有效数字,n 稍大结果就不准。改成
long long可以算到 20!(21! 已超出 64 位整数的表示范围)。 - 把“隐式”的递归层次打印出来,这是体会“递归为什么贵”的最好实验:
#include <iostream> using namespace std; long long fact(int n, int depth = 0) { for (int i = 0; i < depth; ++i) cout << "| "; cout << "进入 fact(" << n << ")" << endl; long long r = (n == 0) ? 1 : n * fact(n - 1, depth + 1); for (int i = 0; i < depth; ++i) cout << "| "; cout << "返回 fact(" << n << ") = " << r << endl; return r; } int main() { cout << "结果: " << fact(4) << endl; return 0; }
运行后可以清楚看到:先一路进入 fact(4) → fact(3) → fact(2) → fact(1) → fact(0),到达边界后再一层层返回。
六、任务 6.6:用递归算法输出斐波那契数列第 n 项(教材程序 6_9.cpp)
教材给出的数学公式:
┌ 1 当 n = 1
F(n) = │ 1 当 n = 2
└ F(n-1) + F(n-2) 当 n > 2
按公式可以画出教材图 6.14 那样的与或节点图,照着图很容易写出递归程序:
#include <iostream> using namespace std; int F(int n) // 递归函数,返回值为整型 { int y; if (n == 1) y = 1; // n 等于 1,y 赋值为 1 else if (n == 2) y = 1; // n 等于 2,y 赋值为 1 else y = F(n - 1) + F(n - 2); // 否则调用 F(n-1)、F(n-2) 相加后赋给 y return y; } int main() { int x, z; cin >> x; // 输入一个整数 z = F(x); // 调用 F(),返回值赋给 z cout << "第" << x << "项的值为: " << z << endl; return 0; }
教材评价:与前面的递推算法相比,递归算法显然更清晰、更简练、更易读、更易理解;但对大多数程序而言,递归算法实现起来效率较低,因为函数自己调用自己会增加时间开销。
效率低的原因就在与或节点图里出现了重复的子树。看 F(5):
F(5)
├── F(4)
│ ├── F(3)
│ │ ├── F(2) = 1
│ │ └── F(1) = 1
│ └── F(2) = 1
└── F(3) <-- 在 F(4) 的子树里已经算过一次了
├── F(2) = 1
└── F(1) = 1
n 越大重复计算越夸张,时间复杂度约为 O(1.618^n),属指数级。改造办法:“算过就存下来”。
#include <iostream> using namespace std; long long memo[100] = {0}; // 记忆化数组,0 表示"还没算过" long long F(int n) { if (n == 1 || n == 2) return 1; // 递归边界 if (memo[n] != 0) return memo[n]; // 已算过,直接取用 return memo[n] = F(n - 1) + F(n - 2); // 算一次并保存 }
同样是用递归的写法,但每个值只算一次,复杂度降为 O(n)。可以在 Linux 下用 time ./fibo 对比朴素递归与记忆化递归跑 n = 40 的耗时差别。
七、6.4 知识拓展:库函数与头文件
教材要点:函数具有强大的功能,其中库函数尤为重要,因为我们可以通过调用库函数使程序变得简单明了;使用库函数需要添加相应的头文件。
教材给了两个思考题,请在 Linux 上编译运行,根据运行结果判断函数的功能:
思考 6.1
#include <iostream> #include <cmath> using namespace std; int main(void) { int number = -1234; cout << "number: " << number << " absolute value: " << abs(number) << endl; return 0; }
结论:abs(num) 的功能是返回参数 num 的绝对值。输出为 number: -1234 absolute value: 1234。
思考 6.2
#include <iostream> #include <cmath> using namespace std; int main(void) { double x = 4.0, result; result = sqrt(x); cout << "The square root of " << x << " is " << result << endl; return 0; }
结论:sqrt(num) 的功能是返回参数 num 的平方根;如果 num 为负,会产生域错误(结果为 NaN),程序里应先判断参数是否合法。
相似例子:附录 D 中常见的数学库函数,都可以照上面的套路动手试一遍:
| 函数 | 功能 | 示例 |
|---|---|---|
| abs(x) | 整数绝对值 | abs(-1234) = 1234 |
| fabs(x) | 浮点绝对值 | fabs(-3.5) = 3.5 |
| sqrt(x) | 平方根 | sqrt(4.0) = 2.0 |
| pow(x, y) | x 的 y 次幂 | pow(2, 10) = 1024 |
| sin(x) / cos(x) | 正弦 / 余弦(弧度) | sin(0) = 0 |
| ceil(x) / floor(x) | 向上 / 向下取整 | ceil(2.1) = 3,floor(2.9) = 2 |
小提示:C 风格的头文件是 math.h,C++ 风格写 cmath;整数绝对值也可来自 cstdlib,而浮点绝对值建议用 fabs 或 std::abs,避免重载选择不当导致丢精度。
八、6.5 思考与实训(Linux + g++ 全解)
实训 6.1:找出并改正程序中的错误
任务:计算 1~8 之间各个自然数的阶乘。教材给出的程序有错误:
#include<iostream> sing namespace std; int p; int main() { int n=0; for(n=1;n<=8;n=n+1) { cout<<n<<"!="<<p(n)<<endl; } return 0; } int p(int) { int k,s=1; for(k=1;k<=n;k=k+1) s=s*k; return s; }
错误分析与改正:
| 位置 | 问题 | 改正 |
|---|---|---|
| 第 2 行 | sing 是拼写错误,关键字应为 using | using namespace std; |
| 第 3 行 | 多余的全局变量 int p;,与函数 p 同名,还使 p(n) 变成“变量后面跟括号” | 删除该行 |
| 第 13 行 | 形参只写了类型 int,没有名字,函数体内却使用了 n | 写成 int p(int n) |
| 第 13 行 | 函数定义在 main 之后,调用前没有声明 | 把定义移到 main 之前,或在 main 前加原型 int p(int n); |
改正后的完整程序:
#include <iostream> using namespace std; int p(int n) // 形参命名,且定义在调用之前 { int s = 1; // 累乘初值必须是 1 for (int k = 1; k <= n; ++k) s = s * k; return s; } int main() { for (int n = 1; n <= 8; ++n) // 顺手去掉多余的 int n=0; cout << n << "!=" << p(n) << endl; return 0; }
运行结果:
1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320
(8! = 40320 仍在 int 范围内;再往上算到 13! 就需要 long long 了。)
实训 6.2:装错信封(错排问题)
任务:一个糊涂人写了 n 封信和 n 个信封,邮寄时把所有信都装错了。设 Dn 为 n 封信装错时可能的种类数,递推公式为:
┌ (n-1) × ( D(n-1) + D(n-2) ) 当 n > 2
D(n) = │ 1 当 n = 2
└ 0 当 n = 1
教材解题思路:题目已给出递推公式,只需按照公式进行递推计算即可。先看清两个边界:D(1) = 0(只有一封信,不可能装错);D(2) = 1(两封信互换)。
先给递推写法:
#include <iostream> using namespace std; int main() { int n; cout << "请输入 n: "; cin >> n; long long d1 = 0, d2 = 1, d = 0; // d1 = D(1),d2 = D(2) if (n == 1) d = d1; else if (n == 2) d = d2; else { for (int i = 3; i <= n; ++i) { d = (long long)(i - 1) * (d1 + d2); d1 = d2; // 滚动更新,只用两个变量 d2 = d; } } cout << "D" << n << "=" << d << endl; return 0; }
也可以按公式直接写成递归,与数学公式一一对应,可读性更好:
long long D(int n) { if (n == 1) return 0; // 递归边界 if (n == 2) return 1; // 递归边界 return (long long)(n - 1) * (D(n - 1) + D(n - 2)); // 递归关系 }
前几项验证:D(1)=0,D(2)=1,D(3)=2,D(4)=9,D(5)=44,D(6)=265。建议 n 控制在 20 以内(long long 的表示范围有限)。
实训 6.3:求各位数字之和
任务:输入一个整数 a(a < 32767),用一个长整型变量存放,求该数每一位数字的和。例如输入 32423,先分解成 3、2、4、2、3,再相加得 14 输出。
教材解题思路:通过一个自定义函数将整数求余分解,返回每一位数,通过主函数相加求和。
下面用本节刚学的递归来做“求余分解”——每次取末位 a % 10,剩下的部分 a / 10 交给下一次调用:
#include <iostream> using namespace std; int digitSum(long a) { if (a == 0) return 0; // 递归边界 return a % 10 + digitSum(a / 10); // 递归关系:末位 + 剩余各位之和 } int main() { long a; cout << "请输入一个整数: "; cin >> a; if (a < 0) a = -a; // 负数取相反数 cout << "各位数字之和为: " << digitSum(a) << endl; return 0; }
如果按教材“递推”的写法(循环逐位分解、主函数累加),核心就是:
long sum = 0; while (a > 0) { sum += a % 10; // 取末位 a /= 10; // 去掉末位 } cout << sum << endl;
实训 6.4:年龄问题
任务:5 个人 A、B、C、D、E 坐在一起。问 A 多大?A 说自己比 B 大 2 岁;问 B,B 说自己比 C 大 2 岁;问 C,C 说自己比 D 大 2 岁;问 D,D 说自己比 E 大 2 岁;最后问 E,E 说 10 岁。问 A 多大?
教材给出的关系:
age[5] = age[4] + 2 age[4] = age[3] + 2 age[3] = age[2] + 2 age[2] = age[1] + 2 age[1] = 10 <-- 递归边界
写成一般式:
age[n] = 10 当 n = 1 age[n] = age[n-1] + 2 当 n > 1
显然这是一个递归问题(1 号是 E,5 号是 A):
#include <iostream> using namespace std; int age(int n) // 1 号是 E,5 号是 A { if (n == 1) return 10; // 递归边界:E 10 岁 return age(n - 1) + 2; // 递归关系:比前一个人大 2 岁 } int main() { cout << "E(第1个人): " << age(1) << " 岁" << endl; cout << "D(第2个人): " << age(2) << " 岁" << endl; cout << "C(第3个人): " << age(3) << " 岁" << endl; cout << "B(第4个人): " << age(4) << " 岁" << endl; cout << "A(第5个人): " << age(5) << " 岁" << endl; return 0; }
输出依次为 10、12、14、16、18,即 A 是 18 岁。
九、6.6 小结(教材要点)
- (1) 使用函数是使程序实现模块化的重要思想:让每个函数完成一个确定的独立任务,程序结构清晰、易读、易调试、易于修改和维护。
- (2) 函数调用存在主从关系:主函数调用其他函数的目的是让被调用函数完成某个计算或操作任务;如为计算则要返回一个计算出来的值,如为操作则不返回数据。有调用就要有返回,在被调用函数末尾写一条
return语句,是值得提倡的好习惯。 - (3) 函数中的形式参数属于局部变量,作用域限定在函数体内。一个函数调用另一个函数时,实际参数是一个具有确定值的表达式,实际参数的类型与个数要与形式参数完全一致,且需一一对应。
- (4) 递归思想是算法设计的有力工具,对于拓展编程思路非常有效;学习和会用与或节点图对编写递归程序十分有用。
十、6.7 知识巩固(教材试题)
【试题 1】 以下函数值的类型是 __。
fun(float x) { float y; y = 3 * x - 4; return y; }
A. int B. 不确定 C. void D. float
答案:D。函数体内 y 是 float,表达式 3 * x - 4 也是实型,函数返回值的类型由定义时决定的类型确定。
【试题 2】 教材 P97 末尾给出如下程序(后续内容在下一页继续):
void f(int v, int w) { int t; t = v; v = w; w = t; // 只交换了两个形参 } int main() { int a = 1, b = 2; f(a, b); // 实参与形参之间是"值传递" cout << a << " " << b << endl; return 0; }
运行结果是 1 2,a、b 并没有被交换。原因是 C++ 默认的参数传递方式是值传递:形参 v、w 只是实参的副本,函数内交换的仅仅是副本。要让函数真正交换实参,需要传引用(void f(int &v, int &w))或传指针——这部分在教材后续章节展开,这里先记住结论。
十一、常见错误与 Linux 调试小贴士
- 忘记递归边界:程序会一直调用自己,最终以
Segmentation fault (core dumped)结束。用打印调用层次(本文第五节的小程序)或 gdb 看调用栈来定位。 - 函数未声明就使用:定义写在 main 之后时,必须在 main 之前加函数原型声明,否则报
was not declared in this scope(实训 6.1 就踩了这个坑)。 - 形参没有名字:
int p(int)作为声明是合法的,但函数体内没法使用这个参数,会报 “未声明” 类错误。 - 类型与精度:float 只有约 7 位有效数字,阶乘、错排很快会超出范围;按需换成
long long/unsigned long long。 - 递归层次过深:Linux 下进程栈空间通常约 8 MB,递归上万层可能栈溢出,应改为递推或用显式栈。
- 编译命令:
g++ -Wall -Wextra -g -o prog prog.cpp,警告不要忽略,-g便于用 gdb 单步观察递归的调用与返回。
十二、知识结构导图
# 递归及其实现(P91-P97) ## 6.3 递归及其实现 ### 两个必备要素 - 递归关系:n! = n × (n-1)! - 递归边界:0! = 1 ### 与或节点图 - 或节点 ○:按条件二选一 - 与节点 ●:先求左边,取最右边节点之值 - 4! 的展开与回代 ### 任务 6.5 递归求 n! - 程序 6_8.cpp(fact 函数) - float 精度有限,改 long long ### 任务 6.6 斐波那契 - F(n) = F(n-1) + F(n-2) - 程序 6_9.cpp - 重复子树导致指数级,可记忆化 ### 递归 vs 递推 - 递推:从初始条件出发 - 递归:从目标出发,到边界再回代 - 递归清晰但增加时间开销 ## 6.4 知识拓展 - 库函数要用相应头文件 - abs:绝对值 - sqrt:平方根,负数产生域错误 ## 6.5 思考与实训 - 6.1 找错改正(4 处) - 6.2 错排 D(n) 递推与递归 - 6.3 各位数字之和(求余分解) - 6.4 年龄问题(递归求 age) ## 6.6 小结 - 模块化思想 - 主从调用、有调用就有返回 - 形参是局部变量,实参类型与个数要一一对应 - 递归是算法设计的有力工具 ## 6.7 知识巩固 - 试题 1:返回值类型 float - 试题 2:值传递不改变实参