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

📚 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;
}

解题步骤图:

以上代码分别使用递归算法解决了斐波那契数列、阶乘计算和最大公约数的问题。通过递归的方式，我们可以简洁地解决这些问题，并且代码具有可读性和可维护性。

📚 总结

递归算法是一种强大的问题求解方法，通过将问题分解为相同类型的子问题，可以高效地解决各种复杂的问题。在编写递归算法时，需要注意定义好基本情况和递归的终止条件，确保算法的正确性和有效性。通过递归算法的练习，我们可以更深入地理解递归思想和算法设计的精妙之处。

⭐️希望本篇文章对你有所帮助。

⭐️如果你有任何问题或疑惑，请随时向提问。

⭐️感谢阅读！