递归函数展开 输出1次
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(1)
6 int n = 1;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(0)
13 int n = 0;
14 printf("time %d: ", n);
15 printf("end\n");
16 }
17 printf("end of %d\n", n);
18 return 0;
19}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(1);
17 return 0;
18}输出2次
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // tellStory(2)
6 int n = 2;
7 printf("time %d: ", n);
8 if (n == 0) {
9 printf("end\n");
10 } else {
11 printf("tell you a story:\n");
12 // tellStory(1)
13 int n = 1;
14 printf("time %d: ", n);
15 if (n == 0) {
16 printf("end\n");
17 } else {
18 printf("tell you a story:\n");
19 // tellStory(0)
20 int n = 0;
21 printf("time %d: ", n);
22 printf("end\n");
23 }
24 printf("end of %d\n", n);
25 }
26 printf("end of %d\n", n);
27 return 0;
28}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(2);
17 return 0;
18}输出3次
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n = 3;
6 printf("time %d: ", n);
7 if (n == 0) {
8 printf("end\n");
9 } else {
10 printf("tell you a story:\n");
11 // tellStory(2)
12 int n = 2;
13 printf("time %d: ", n);
14 if (n == 0) {
15 printf("end\n");
16 } else {
17 printf("tell you a story:\n");
18 // tellStory(1)
19 int n = 1;
20 printf("time %d: ", n);
21 if (n == 0) {
22 printf("end\n");
23 } else {
24 printf("tell you a story:\n");
25 // tellStory(0)
26 int n = 0;
27 printf("time %d: ", n);
28 printf("end\n");
29 }
30 printf("end of %d\n", n);
31 }
32 printf("end of %d\n", n);
33 }
34 printf("end of %d\n", n);
35 return 0;
36}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4void tellStory(int n) {
5 printf("time %d: ", n);
6 if (n == 0) {
7 printf("end\n");
8 return;
9 }
10 printf("tell you a story:\n");
11 tellStory(n - 1);
12 printf("end of %d\n", n);
13}
14
15int main() {
16 tellStory(3);
17 return 0;
18}阶乘递归函数展开 求2的阶乘
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN;
6 int n = 2;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 1;
12 if (n == 1) {
13 factorialN = 1;
14 }
15 }
16 factorialN = n * factorialN;
17 }
18 cout << factorialN << endl;
19 return 0;
20}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(2);
13 cout << factorialN << endl;
14 return 0;
15}求3的阶乘
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 3;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 2;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 1;
17 if (n == 1) {
18 factorialN = 1;
19 }
20 }
21 factorialN = n * factorialN;
22 }
23 }
24 factorialN = n * factorialN;
25 }
26 cout << factorialN << endl;
27 return 0;
28}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(2);
13 cout << factorialN << endl;
14 return 0;
15}求4的阶乘
非函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int factorialN = 0;
6 int n = 4;
7 if (n == 1) {
8 factorialN = 1;
9 } else {
10 {
11 int n = 3;
12 if (n == 1) {
13 factorialN = 1;
14 } else {
15 {
16 int n = 2;
17 if (n == 1) {
18 factorialN = 1;
19 } else {
20 {
21 int n = 1;
22 if (n == 1) {
23 factorialN = 1;
24 }
25 }
26 factorialN = n * factorialN;
27 }
28 }
29 factorialN = n * factorialN;
30 }
31 }
32 factorialN = n * factorialN;
33 }
34 cout << factorialN << endl;
35 return 0;
36}函数调用方式
1#include <bits/stdc++.h>
2using namespace std;
3
4int factorial(int n) {
5 if (n == 1) {
6 return 1;
7 }
8 return n * factorial(n - 1);
9}
10
11int main() {
12 int factorialN = factorial(2);
13 cout << factorialN << endl;
14 return 0;
15}递归-知识总结 递归概念 递推是一种解决问题的方式，即使用函数自己调用自己的方式进行循环求解。通常用来解决可以通过把问题规模逐渐缩小从而求解的问题。
常见的使用递递归解的场景有： 有明显递推关系 需要使用分治思想 数据结构操作
递归过程中使用的函数被称作递归函数。递归函数需要包含两个部分： 基本情况：结束递归调用的情况； 递归情况：自己调用自己的情况。
算法评价 递归算法不需要存储数据，因此空间复杂度往往很低，但是由于其调用的复杂性，时间复杂度需要具体问题具体分析。 递归示例 等差数列 递推公式：a[n] = a[n - 1] + d
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) + d;
6}等比数列 递推公式：a[n] = a[n-1] * q
1int a(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return a(n - 1) * q;
6}斐波那契数列 递推公式：f[n] = f[n-1] + f[n-2]
1int fibonacci(int n) {
2 if (n == 1 || n == 2) {
3 return 1;
4 }
5 return fibonacci(n - 1) + fibonacci(n - 2);
6}递推求和 sum(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1 递推公式：s[n] = s[n-1] + n
1int sum(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return sum(n - 1) + n;
6}递推求阶乘 n! = n × (n - 1) × (n - 2) × ... × 3 × 2 × 1 递推公式：f[n] = f[n-1] * n
1int factorial(int n) {
2 if (n == 1) {
3 return 1;
4 }
5 return factorial(n - 1) * n;
6}错误的题目要弄懂，不会的千万要来问老师⚠️
总结作业非常重要，请务必认真完成✔️
考试只有一次提交机会，请务必本地检查正确后再提交❇️
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
递归-选择题 递归函数是什么？ A) 一个永远不返回的函数 B) 一个调用自身的函数 C) 一个循环函数 D) 一个总是返回固定值的函数
在递归函数中，什么是基本案例（base case）？ A) 函数的初始调用 B) 阻止递归继续的条件 C) 每次递归调用的结果 D) 递归的第一步
在递归函数中，如果没有正确定义基本案例，会发生什么？ A) 函数将返回错误的结果 B) 函数将不会执行 C) 函数可能会无限循环下去 D) 函数将变成一个普通函数
递归函数是否一定包含条件判断语句？ A) 是 B) 不是
通常情况下，递归函数都是有参数的？ A) 是 B) 不是
递归函数是否一定要有return语句？ A) 是 B) 不是
以下哪种情况最适合使用递归？ A) 当问题可以分解为相似的子问题时 B) 当需要快速计算结果时 C) 当问题不能定义为重复任务时 D) 在处理大型数据集时
下面哪个是计算阶乘的递归函数？ A)
int factorial(int n) {
return n * factorial(n - 1);
}B)
1int factorial(int n) {
2 if (n <= 1) {
3 return 1;
4 } else {
5 return n * factorial(n);
6 }
7}C)
1int factorial(int n) {
2 if (n <= 1) {
3 return 1;
4 } else {
5 return n * factorial(n - 1);
6 }
7}D)
int factorial(int n) {
return n;
}如何用递归实现一个函数来计算从 1 到 n 的总和，即计算：1 + 2 + ... + n ？ A)
int sum(int n) {
return n + sum(n - 1);
}B)
1int sum(int n) {
2 if (n == 1) {
3 return 1;
4 } else {
5 return n + sum(n);
6 }
7}C)
1int sum(int n) {
2 if (n <= 1) {
3 return n;
4 } else {
5 return n - sum(n - 1);
6 }
7}D)
1int sum(int n) {
2 if (n <= 1) {
3 return 1;
4 } else {
5 return n + sum(n - 1);
6 }
7}如何用递归实现一个计算斐波那契数列第 n 项的函数？ A)
1int fibonacci(int n) {
2 if (n <= 2) {
3 return n;
4 } else {
5 return fibonacci(n - 1) + fibonacci(n - 2);
6 }
7}B)
int fibonacci(int n) {
return fibonacci(n - 1) + fibonacci(n - 2);
}C)
1int fibonacci(int n) {
2 if (n == 0) {
3 return 0;
4 } else {
5 return fibonacci(n - 1) + fibonacci(n - 2);
6 }
7}D)
1int fibonacci(int n) {
2 if (n <= 2) {
3 return 1;
4 } else {
5 return fibonacci(n - 1) + fibonacci(n - 2);
6 }
7}递归-选择题答案 B 解析：递归函数是一个在其定义中调用自身的函数。
B 解析：基本案例是递归调用中停止递归继续的条件，防止无限循环。
C 解析：没有基本案例，递归函数可能会无限循环下去，导致栈溢出等问题。
A 解析：是的，递归函数通常需要一个条件判断语句来确定何时停止递归（即达到基本案例）。
A 解析：递归函数的参数可以帮助我们决定是进入基本情况还是进入递归调用。
A 解析：是的，递归函数需要有 return 语句来返回计算结果或调用自身。
A 解析：当问题可以分解为一系列相似的、更小的子问题时，使用递归是最合适的。
C 解析：阶乘的递归公式是：f(n)=f(n-1)*n, 其中n≥1
D 解析：求和的递归公式是：f(n)=f(n-1)+n, 其中n≥1
D 解析：斐波那契数列的递归公式是：f(n)=f(n-1)+f(n-2), 其中n≥2
L2104题解+参考代码 题目链接 递归函数：L2104
题解 题目要求我们实现一个有三个参数的递归函数 w(a, b, c)，按照给定的规则进行计算。我们只需要实现递归函数并调用它来计算结果。
算法步骤 定义函数 w： 输入：三个整数 a、b、c。 输出：根据规则计算的结果。 如果 a、b、c 中任意一个小于等于0，返回1。 如果 a、b、c 中任意一个大于10，返回 w(10, 10, 10)。 否则，按照递归规则计算结果。 主函数： 读取输入的三个整数 a、b、c。 调用函数 w(a, b, c) 计算结果并输出。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <iostream>
2using namespace std;
3
4// 定义递归函数 w
5int w(int a, int b, int c) {
6 // 如果 a, b, c 中任意一个小于等于0
7 if (a <= 0 || b <= 0 || c <= 0) {
8 return 1;
9 }
10
11 // 如果 a, b, c 中任意一个大于10
12 if (a > 10 || b > 10 || c > 10) {
13 return w(10, 10, 10);
14 }
15
16 // 按照递归规则计算
17 return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
18}
19
20int main() {
21 // 读取输入
22 int a, b, c;
23 cin >> a >> b >> c;
24
25 // 调用递归函数计算结果
26 int result = w(a, b, c);
27
28 // 输出结果
29 cout << result << endl;
30
31 return 0;
32}L2105题解+参考代码 题目链接 数数小木块：L2105
题解 给定图像显示了一个堆积的立方体结构，其中第1层有1个立方体，第2层有3个立方体，第3层有6个立方体，以此类推。每一层的立方体数量构成一个三角形数列，第n层的立方体数量是前n个正整数的和。
算法步骤 定义递归函数 calculateLayerBlocks： 输入：整数 n，表示当前层数。 返回值：第 n 层的立方体数量。 如果 n 为1，返回 1。 否则，返回 n 加上 calculateLayerBlocks(n - 1) 的结果。 定义递归函数 calculateTotalBlocks： 输入：整数 n，表示总层数。 返回值：前 n 层的立方体总数量。 如果 n 为1，返回 1。 否则，返回第 n 层的立方体数量加上 calculateTotalBlocks(n - 1) 的结果。 主函数： 读取输入的整数 n。 调用递归函数 calculateTotalBlocks(n) 计算结果并输出。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4// 递归函数计算第 n 层的立方体数量
5int calculateLayerBlocks(int n) {
6 if (n == 1) {
7 return 1;
8 } else {
9 return n + calculateLayerBlocks(n - 1);
10 }
11}
12
13// 递归函数计算前 n 层的立方体总数量
14int calculateTotalBlocks(int n) {
15 if (n == 1) {
16 return 1;
17 } else {
18 return calculateLayerBlocks(n) + calculateTotalBlocks(n - 1);
19 }
20}
21
22int main() {
23 // 读取输入
24 int n;
25 cin >> n;
26
27 // 调用递归函数计算结果
28 int totalBlocks = calculateTotalBlocks(n);
29
30 // 输出结果
31 cout << totalBlocks << endl;
32
33 return 0;
34}