C++算法·递推递归

递推递归定义

递推与递归对比说明：

1. 递推（迭代）：

• 特点：自底向上，显式使用循环
• 优势：效率高（无函数调用开销）

2. 递归：

• 特点：自顶向下，函数自我调用
• 优势：代码简洁，直观反映数学定义
• 缺陷：存在重复计算

3. 应用选择：

• 优先用递推：存在明显状态转移方程（DP问题）
• 适合用递归：问题可自然分解为子问题（树形结构）

递推递归例图

左边的例子是用递推做阶乘
执行操作$5\times 4\times 3\times 2\times 1$

右边的例子是用递归做阶乘
执行操作$1\times 2\times 3\times 4\times 5$

模板代码(阶乘版)

#include <iostream>
using namespace std;
#define int long long
int n;//从1~n的阶乘
int ditui(int x){if(x==1)return x;//完成条件，终止递推return x*ditui(x-1);
}
int digui(int x){if(x==n)return x;//完成条件，终止递归return x*digui(x+1);
}
signed main(){cin>>n;cout <<ditui(n)<<endl;//从顶部开始往下cout <<digui(1)<<endl;//从底部开始往上return 0;
}

看这模板很简单

分析下时间复杂度（看在什么时候使用合适）避免超时$TLE(Time$ $Limit$ $Exceeded)$

方案	时间复杂度	空间复杂度	适用场景
普通递推	O(n)	O(1)	线性结构问题
普通递归	O(2ⁿ)	O(n)	教学演示
记忆化递归	O(n)	O(n)	树形结构问题
尾递归	O(n)	O(1)	支持尾调用优化的语言

总结：递推是更高效的，但是递归更方便理解

例题实战

$题目传送门$

P1255 数楼梯

题目描述

楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例 #1

输入 #1

4

输出 #1

5

说明/提示

• 对于 $60\%$ 的数据，$N\le 50$；
• 对于 $100\%$ 的数据，$1\le N\le 5000$。

分析

题目给出的算法标签除了递推递归
还有之前讲过的高精！！
仔细看数据范围，5000的$n$看起来不大
实际上算上去会直接爆炸,longlong都装不下
这时候就要高精了(其实是交了一次然后炸了/bushi)
点→高精度运算文章传送
继续讲，题面很简单就是给你阶梯，让你选择怎么走
2种选择

1. 走一步
2. 走两步

可以先列举几个找找规律
看能不能直接列递推式
$n=1$时，$ans=1$
$n=2$时，$ans=2$
$n=3$时，$ans=3$
$n=4$时，$ans=5$
$n=5$时，$ans=8$
…
聪明的你可能已经发现了
这是一个斐波那契数列！
也就是说
只需结合高精算法就可以轻松攻破$AC$的大门
话不多说上代码

例题代码

#include <iostream>
#include <string>
using namespace std;
string sum[10005];//注意这里需要用string定义
int a[100001],b[100001],c[100001];
string add(string a_,string b_){int len_a=a_.size();int len_b=b_.size();for(int i=0;i<len_a;i++){a[i]=a_[len_a-1-i]-'0';}for(int i=0;i<len_b;i++){b[i]=b_[len_b-1-i]-'0';}int len_c=max(len_a,len_b),t=0;for(int i=0;i<len_c;i++){c[i]=a[i]+b[i]+t;if(c[i]>=10){t=1;c[i]%=10;}else{t=0;}}if(t){len_c++;c[len_c-1]=1;}string s;for(int i=len_c-1;i>=0;i--){s+=c[i]+'0';}return s;
}//高精算法，详细介绍可以看我之前的文章，链接在上面
int main(){int x;cin>>x;//台阶数sum[1]="1",sum[2]="2";//初始化for(int i=3;i<=x;i++){sum[i]=add(sum[i-1],sum[i-2]);//斐波那契}cout <<sum[x];//输出总和return 0;
}

题单推荐

$递推递归题单$
题单和例题均来自$洛谷$

~ $完结撒花$ ~

附：高精度运算文章传送
没弄懂高精或者想要了解高精度运算的可以看看这篇文章↑
推荐$洛谷$作为你的刷题区域
下一篇预告：结构体或者贪心（把前面的补完）