差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
| 程序设计基础:第5章 [2026/10/06 22:18] – 创建 张叶安 | 程序设计基础:第5章 [2026/10/06 22:37] (当前版本) – 添加本节知识结构思维导图 张叶安 | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| {{ : | {{ : | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ====== 递归及其实现:知识总结与教程 ====== | ||
| + | |||
| + | '' | ||
| + | |||
| + | ===== 一、递归的两个必备要素 ===== | ||
| + | |||
| + | 教材用**求 n!** 这一个任务贯穿全节。 | ||
| + | |||
| + | 解题思路(教材要点):当 n ≥ 0 时,求 n! 的问题可以转化为求 n×(n-1)! 的新问题,而求 (n-1)! 的解法与原来求 n! 的解法相同,只是运算对象由 n 变成了 n-1;每转化一次新问题,运算对象就递减 1,直到递减至 0 时阶乘的值为 1,递归结束。 | ||
| + | |||
| + | 写成数学形式: | ||
| + | |||
| + | < | ||
| + | ┌ 1 当 n = 0 时 | ||
| + | n! = │ | ||
| + | └ n × (n-1)! | ||
| + | </ | ||
| + | |||
| + | 由此得出写递归函数的**两个必备要素**: | ||
| + | |||
| + | * **递归关系(递推公式)**: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) 这个整体 | " | ||
| + | |||
| + | **相似例子:4! 的与或节点图**(教材用 3! 举例,此处换成 4!,结构与教材图 6.8、图 6.10 完全一致): | ||
| + | |||
| + | < | ||
| + | fact(4) | ||
| + | | ||
| + | | ||
| + | ├── D: fact(3) | ||
| + | └── E: 4 * fact(3) | ||
| + | </ | ||
| + | |||
| + | 展开与回代(教材的" | ||
| + | |||
| + | < | ||
| + | 展开(调用) | ||
| + | fact(4) = 4 * fact(3) | ||
| + | fact(3) = 3 * fact(2) | ||
| + | fact(2) = 2 * fact(1) | ||
| + | fact(1) = 1 < | ||
| + | </ | ||
| + | |||
| + | 对照教材图 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)===== | ||
| + | |||
| + | 把教材程序去掉注释头和逐行注释后,逻辑如下: | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 << " | ||
| + | else | ||
| + | { | ||
| + | y = fact(n); | ||
| + | cout << n << " | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | Linux 下的编译与运行(务必上机跑一遍,弄清递归是如何进行的): | ||
| + | |||
| + | <code bash> | ||
| + | g++ -Wall -o fact fact.cpp | ||
| + | ./fact | ||
| + | 您要查询第几项? | ||
| + | 5!=120 | ||
| + | </ | ||
| + | |||
| + | 两点自己动手的改进: | ||
| + | |||
| + | * 教材把返回值定为 float,float 只有约 7 位有效数字,n 稍大结果就不准。改成 '' | ||
| + | * 把" | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | using namespace std; | ||
| + | |||
| + | long long fact(int n, int depth = 0) | ||
| + | { | ||
| + | for (int i = 0; i < depth; ++i) cout << " | ||
| + | cout << " | ||
| + | |||
| + | long long r = (n == 0) ? 1 : n * fact(n - 1, depth + 1); | ||
| + | |||
| + | for (int i = 0; i < depth; ++i) cout << " | ||
| + | cout << " | ||
| + | return r; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | cout << " | ||
| + | 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) | ||
| + | </ | ||
| + | |||
| + | 按公式可以画出教材图 6.14 那样的与或节点图,照着图很容易写出递归程序: | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 << " | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 教材评价:与前面的递推算法相比,递归算法显然更清晰、更简练、更易读、更易理解;但对大多数程序而言,递归算法实现起来效率较低,因为函数自己调用自己会增加时间开销。 | ||
| + | |||
| + | 效率低的原因就在**与或节点图里出现了重复的子树**。看 F(5): | ||
| + | |||
| + | < | ||
| + | F(5) | ||
| + | ├── F(4) | ||
| + | │ | ||
| + | │ | ||
| + | │ | ||
| + | │ | ||
| + | └── F(3) <-- 在 F(4) 的子树里已经算过一次了 | ||
| + | ├── F(2) = 1 | ||
| + | └── F(1) = 1 | ||
| + | </ | ||
| + | |||
| + | n 越大重复计算越夸张,时间复杂度约为 O(1.618^n),属指数级。改造办法:" | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 下用 '' | ||
| + | |||
| + | ===== 七、6.4 知识拓展:库函数与头文件 ===== | ||
| + | |||
| + | 教材要点:函数具有强大的功能,其中库函数尤为重要,因为我们可以通过调用库函数使程序变得简单明了;**使用库函数需要添加相应的头文件**。 | ||
| + | |||
| + | 教材给了两个思考题,请在 Linux 上编译运行,根据运行结果判断函数的功能: | ||
| + | |||
| + | **思考 6.1** | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | #include < | ||
| + | using namespace std; | ||
| + | |||
| + | int main(void) | ||
| + | { | ||
| + | int number = -1234; | ||
| + | cout << " | ||
| + | << | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 结论:abs(num) 的功能是**返回参数 num 的绝对值**。输出为 '' | ||
| + | |||
| + | **思考 6.2** | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | #include < | ||
| + | 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 风格的头文件是 '' | ||
| + | |||
| + | ===== 八、6.5 思考与实训(Linux + g++ 全解)===== | ||
| + | |||
| + | ==== 实训 6.1:找出并改正程序中的错误 ==== | ||
| + | |||
| + | 任务:计算 1~8 之间各个自然数的阶乘。教材给出的程序有错误: | ||
| + | |||
| + | <code cpp> | ||
| + | # | ||
| + | sing namespace std; | ||
| + | int p; | ||
| + | int main() | ||
| + | { | ||
| + | int n=0; | ||
| + | for(n=1; | ||
| + | { | ||
| + | cout<< | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | int p(int) | ||
| + | { | ||
| + | int k,s=1; | ||
| + | for(k=1; | ||
| + | s=s*k; | ||
| + | return s; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 错误分析与改正: | ||
| + | |||
| + | ^ 位置 ^ 问题 ^ 改正 ^ | ||
| + | | 第 2 行 | '' | ||
| + | | 第 3 行 | 多余的全局变量 '' | ||
| + | | 第 13 行 | 形参只写了类型 '' | ||
| + | | 第 13 行 | 函数定义在 main 之后,调用前没有声明 | 把定义移到 main 之前,或在 main 前加原型 '' | ||
| + | |||
| + | 改正后的完整程序: | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 << " | ||
| + | |||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 运行结果: | ||
| + | |||
| + | < | ||
| + | 1!=1 | ||
| + | 2!=2 | ||
| + | 3!=6 | ||
| + | 4!=24 | ||
| + | 5!=120 | ||
| + | 6!=720 | ||
| + | 7!=5040 | ||
| + | 8!=40320 | ||
| + | </ | ||
| + | |||
| + | (8! = 40320 仍在 int 范围内;再往上算到 13! 就需要 '' | ||
| + | |||
| + | ==== 实训 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(两封信互换)。 | ||
| + | |||
| + | 先给递推写法: | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | using namespace std; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int n; | ||
| + | cout << " | ||
| + | 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 << " | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 也可以按公式直接写成递归,与数学公式一一对应,可读性更好: | ||
| + | |||
| + | <code cpp> | ||
| + | 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 输出。 | ||
| + | |||
| + | 教材解题思路:通过一个自定义函数将整数求余分解,返回每一位数,通过主函数相加求和。 | ||
| + | |||
| + | 下面用本节刚学的递归来做" | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 << " | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 如果按教材" | ||
| + | |||
| + | <code cpp> | ||
| + | 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): | ||
| + | |||
| + | <code cpp> | ||
| + | #include < | ||
| + | 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 << " | ||
| + | cout << " | ||
| + | cout << " | ||
| + | cout << " | ||
| + | cout << " | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 输出依次为 10、12、14、16、18,即 **A 是 18 岁**。 | ||
| + | |||
| + | ===== 九、6.6 小结(教材要点)===== | ||
| + | |||
| + | - **(1)** 使用函数是使程序实现**模块化**的重要思想:让每个函数完成一个确定的独立任务,程序结构清晰、易读、易调试、易于修改和维护。 | ||
| + | - **(2)** 函数调用存在**主从关系**:主函数调用其他函数的目的是让被调用函数完成某个计算或操作任务;如为计算则要返回一个计算出来的值,如为操作则不返回数据。有调用就要有返回,在被调用函数末尾写一条 '' | ||
| + | - **(3)** 函数中的**形式参数属于局部变量**,作用域限定在函数体内。一个函数调用另一个函数时,实际参数是一个具有确定值的表达式,实际参数的类型与个数要与形式参数完全一致,且需一一对应。 | ||
| + | - **(4)** **递归思想是算法设计的有力工具**,对于拓展编程思路非常有效;学习和会用**与或节点图**对编写递归程序十分有用。 | ||
| + | |||
| + | ===== 十、6.7 知识巩固(教材试题)===== | ||
| + | |||
| + | **【试题 1】** 以下函数值的类型是 ______。 | ||
| + | |||
| + | <code cpp> | ||
| + | fun(float x) | ||
| + | { | ||
| + | float y; | ||
| + | y = 3 * x - 4; | ||
| + | return y; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | A. int B. 不确定 C. void D. float | ||
| + | |||
| + | 答案:**D**。函数体内 '' | ||
| + | |||
| + | **【试题 2】** 教材 P97 末尾给出如下程序(后续内容在下一页继续): | ||
| + | |||
| + | <code cpp> | ||
| + | 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; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | 运行结果是 '' | ||
| + | |||
| + | ===== 十一、常见错误与 Linux 调试小贴士 ===== | ||
| + | |||
| + | * **忘记递归边界**:程序会一直调用自己,最终以 '' | ||
| + | * **函数未声明就使用**:定义写在 main 之后时,必须在 main 之前加函数原型声明,否则报 '' | ||
| + | * **形参没有名字**:'' | ||
| + | * **类型与精度**:float 只有约 7 位有效数字,阶乘、错排很快会超出范围;按需换成 '' | ||
| + | * **递归层次过深**:Linux 下进程栈空间通常约 8 MB,递归上万层可能栈溢出,应改为递推或用显式栈。 | ||
| + | * **编译命令**:'' | ||
| + | |||
| + | ===== 十二、知识结构导图 ===== | ||
| + | |||
| + | ```mdk height=560 | ||
| + | # 递归及其实现(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:值传递不改变实参 | ||
| + | ``` | ||
| + | |||