当前位置：首页 > news >正文

13-C++算法笔记-递归

news 2025/8/2 20:53:13

📚 Introduction

递归是一种常用的算法设计和问题求解方法。它基于问题可以分解为相同类型的子问题，并通过解决子问题来解决原始问题的思想。递归算法在实际编程中具有广泛的应用。

🎯 递归算法解决问题的特点

递归算法具有以下特点：

问题可以分解为相同类型的子问题。
递归算法通过解决子问题来解决原始问题。
递归算法在解决问题时使用自己调用自己的方式。

📝 递推算法练习题

🐰 1. 斐波那契数列

题目描述:
斐波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面两个数之和。现在给定一个正整数n，要求计算斐波那契数列的第n个数。

💡 思路解析:

基本情况: 当n为1或2时，直接返回1。
递归过程: 对于其他n，递归计算斐波那契数列的第n-1和n-2个数，并将它们相加。

#include <iostream>
using namespace std;int fibonacci(int n) {if (n <= 2) {return 1;}return fibonacci(n - 1) + fibonacci(n - 2);
}int main() {int n = 6;cout << "斐波那契数列的第" << n << "个数为：" << fibonacci(n) << endl;return 0;
}

解题步骤图:

🔄 2. 阶乘计算

题目描述:
阶乘是指从1乘积到给定的正整数n。现在给定一个正整数n，要求计算n的阶乘。

💡 思路解析:

基本情况: 当n为0或1时，直接返回1。
递归过程: 对于其他n，递归计算n-1的阶乘，并将其乘以n。

#include <iostream>
using namespace std;int factorial(int n) {if (n <= 1) {return 1;}return n * factorial(n - 1);
}int main() {int n = 5;cout << n << "的阶乘为：" << factorial(n) << endl;return 0;
}

解题步骤图:

📏 3. 最大公约数

题目描述:
给定两个正整数a和b，要求计算它们的最大公约数。

💡 思路解析:

基本情况: 当b等于0时，直接返回a。
递归过程: 对于其他情况，递归计算b和a除以b的余数的最大公约数。

#include <iostream>
using namespace std;int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}int main() {int a = 24;int b = 36;cout << a << "和" << b << "的最大公约数为：" << gcd(a, b) << endl;return 0;
}