算法——递推

前言

递推算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解递推。

一、什么是递推

递推算法（也称为递归算法或迭代算法，视具体实现而定）是一种通过已知信息逐步推导未知信息的算法设计技术。它通常用于解决那些可以分解为相似子问题的问题。递推算法的核心思想是利用已经计算出的结果来推导新的结果，从而避免重复计算，提高效率。

二、递推算法的分类

递推算法可以分为顺推和逆推两种：
顺推法：从已知条件出发，逐步推算出要解决的问题的方法。它通常用于求解序列的下一项或达到某个特定状态所需的步骤。例如，斐波那契数列的求解就可以使用顺推法。

逆推法：从已知问题的结果出发，用迭代表达式逐步推算出问题的初始条件。它是顺推法的逆过程，通常用于求解逆向问题或回溯问题。

三、递推算法的特点

高效性：递推算法避免了数据进出栈的过程，直接从边界出发，直到求出函数值。因此，相对于递归算法，递推算法通常具有更高的效率。

简单性：递推算法将复杂的计算过程转化为简单的重复步骤，使得算法易于理解和实现。

适用性：递推算法适用于求解具有递推关系的问题，如数列、动态规划等。

四、递推算法的应用

数列求解：递推算法在求解数列问题中具有重要作用。例如，斐波那契数列、等差数列、等比数列等都可以通过递推算法来求解。

动态规划：动态规划是一种解决最优化问题的算法思想，它通常使用递推关系来求解最优解。递推算法在动态规划中具有广泛的应用。

组合数学：递推算法在组合数学中也有重要作用。例如，求解排列、组合、概率等问题时，经常需要使用递推关系来简化计算。

五、递推算法的设计步骤

1.确定数据项：根据题目要求，确定需要求解的数据项。

2.找到递推关系式：通过分析题目，找到数据项之间的递推关系式。

3.设计递推程序：根据递推关系式，设计递推程序来求解问题。
找到递推的终点：确定递推过程的终点，即何时停止递推。

4.输出结果：按要求输出求解结果。

六、递推算法与递归算法的比较

实现方式：递推算法是从边界出发，逐步求解问题；而递归算法则是通过函数不断调用自身来求解问题。

效率：递推算法通常比递归算法更高效，因为它避免了数据进出栈的过程。

适用性：递推算法适用于求解具有明确递推关系的问题；而递归算法则更适用于求解具有递归性质的问题，如树的遍历、图的搜索等。

七、经典例题

1.斐波那契数列

（帅哥这个蓝色字体可以点进去看原题）

代码题解

class Solution {
public:int fib(int n) {int a[31];a[0]=0;a[1]=1;for(int i=2;i<=n;i++){a[i]=a[i-1]+a[i-2];}return a[n];}
};

2.爬楼梯

（帅哥这个蓝色字体可以点进去看原题）

代码题解

class Solution {
public:int climbStairs(int n) {int a[46];a[0]=1;//在第0阶就是1a[1]=1;//从第0阶上到1阶就只有一种方法，所以也是1for(int i=2;i<=n;i++){a[i]=a[i-1]+a[i-2];//爬到i阶楼梯等于前面两个方案数之和}return a[n];}
};

3.杨辉三角 II

代码题解1

class Solution {
public:vector<int> getRow(int rowIndex) {int a[34][34];a[0][0]=1;for(int i=0;i<=rowIndex;i++){for(int j=0;j<=i;j++){if(j==0||j==i) a[i][j]=1;//每一层首位元素都是1else a[i][j]=a[i-1][j]+a[i-1][j-1];}}vector<int> ret;for(int j=0;j<=rowIndex;j++){ret.push_back(a[rowIndex][j]);}return ret;}
};

代码题解2

class Solution {
public:vector<int> getRow(int rowIndex) {int a[2][34];int pre=0,now=1;//pre代表上一层，now代表这一层a[pre][0]=1;for(int i=1;i<=rowIndex;i++){for(int j=0;j<=i;j++){if(!j||j==i)a[now][j]=1;else a[now][j]=a[pre][j-1]+a[pre][j];}pre^=1;//pre与now的值互相转换，也就是0变为1，1变为0now^=1;}vector<int>ret;for(int i=0;i<=rowIndex;i++){ret.push_back(a[pre][i]);}return ret;}
};

八、总结

综上所述，递推算法是一种简单而高效的算法思想，在求解具有递推关系的问题中具有重要作用。在设计和实现递推算法时，需要仔细分析题目要求，找到正确的递推关系式，并设计合理的递推程序来求解问题。

结语

学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，不会的地方就问，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，我相信你一定能行。

关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家。