目录

程序设计基础_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! 中的对应 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

两点自己动手的改进:

#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 小结(教材要点)

十、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 调试小贴士

十二、知识结构导图

# 递归及其实现(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:值传递不改变实参