前言：递推最通俗的理解就是数列，递推和数列的关系就好比算法和数据结构的关系，数列有点像数据结构中的顺序表，而递推就是一个循环或者迭代的过程的枚举过程
1.斐波那契数列
斐波那契数形成的序列称为斐波那契数列，该数列由0和1开始，后面的每一项数字都是前面两项数字之和，也就是：
F[0]=0 F[1]=1
0 1 1 2 3 5 8 13 21 34 根据规律我们很容易推得下面递推公式：
F[n]=F[n-1]+F[n-2] 其中n>1
递归函数有两大要点：1.递归的终止条件 2.递归操作（根据上文已推f(n-1)+f(n-2)）
public int fib(int n) {
//递归条件
if(n<2){
return n;
}
//递归操作
return fib(n-1)+fib(n-2);
}- 递归用的用的数据结构其实是栈（先进先出），是自顶向下的算法
- 因为第一项第二项我们是很容易得到的，所以可以当做递归结束的出口
- 利用递推公式逐步的计算每一项的值
- 最后返回结果即可
2.泰波那契数列
泰波那契数列Tn的定义如下：
T(0)=0 T(1)=1 T(2)=1
且在n>2的条件下T(n)=T(n-1)+T(n-2)+T(n-3) 给你一个整数n,返回T(n)的值
如果已经理解了斐波那契数列，那么这个问题也不难，只不过递归条件，递归操作多加一点东西而已，看代码：
public int tribonacci(int n) {
if(n<2){
return n;
}
if(n==2){
return 1;
}
return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
}0 <= n <= 37 看这个数据范围，当递归这种情况的时候，时间复杂度是很高的，所以不出意外的超时了，但是这种方法也可以用别的方法去做，比如记忆化数组以及动态规划，这部分在这里先不讲了，后面会详细介绍的
3.斐波那契数列的问题转换
1.爬楼梯问题
给定一个n(1<=n<=45)代表总共有n阶台阶，一开始在第n阶台阶， 每次可以爬1或者2个台阶，问总共有多少种不同的方式可以爬到楼顶
假设我们现在已经在第n层，我们是不是可以由第n-1层或者是第n-2层跳过来的呢？所以我们可以推得如下的递推关系式 F[i]=F[i-1]+F[i-2]
于是我们可以发现这个递推公式和斐波那契数列公式极为相像，既然解题思路也是一致，只需要修改递归条件就可以解除本题，但是由于这种的时间复杂度过高
一般是从递推->记忆化搜索->动态规划->状态压缩 进行优化
//递归
public int numWays(int n) {
if(n==0){
return 1;
}
if(n==1){
return 1;
}
if(n==2){
return 2;
}
//递归操作
return numWays(n-1)+numWays(n-2);
}2.二维递推问题（后面细聊，这部分对于新手来说确实有些困难）
leetcode题单：
斐波那契数
public int fib(int n) {
if(n<2){
return n;
}
return fib(n-1)+fib(n-2);
}第N个泰波那契数
public int tribonacci(int n) {
if(n<2){
return n;
}
int[] dp=new int[n+1];
dp[0]=0;
dp[1]=1;
dp[2]=1;
for(int i=3;i<dp.length;i++){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; }
return dp[n];
}青蛙跳台阶问题
private static final int[] meno=new int[101];
//递归
public int numWays(int n) {
if(n==0||n==1){
meno[n]=1;
return 1;
}
if(meno[n]==0){
meno[n]=(numWays(n-1)+numWays(n-2))%1000000007;
}
return meno[n];
}三步问题文章来源：https://www.toymoban.com/news/detail-619801.html
public int waysToStep(int n) {
if(n<2){
return 1;
}
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
dp[2]=2;
for(int i=3;i<dp.length;i++){
dp[i]=(((dp[i-1]+dp[i-2])%1000000007)+dp[i-3])%1000000007;
}
return dp[n];
}爬楼梯文章来源地址https://www.toymoban.com/news/detail-619801.html
private static final int[] meno=new int[101];
public int climbStairs(int n) {
if(n==0||n==1){
meno[n]=1;
return 1;
}
if(meno[n]==0){
meno[n]=climbStairs(n-1)+climbStairs(n-2);
}
return meno[n];
}到了这里，关于一起学算法（递推篇）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
