递归/递推
Mike_L
·
2024-06-24 15:10:32
·
算法·理论
引入
有一个很经典的故事：
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“太困了不讲了不讲了”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。”于是都回去睡觉了。
（双引号不规范，仅供示意）
这个故事就是递归的经典应用。
递归是什么
某同学：递归就是一个函数自己调用自己的过程，它的缺点就是时间复杂度，容易陷入死循环，所以要加一个判断条件让它能够退出，否则程序会永无休止地运行下去，直到进程消失。
这就是递归。
所以，一开始的故事可以抽象成：
void 讲故事()
{
if (困了)
return;
讲故事();
回去睡觉;
}
这就是递归，函数自己调用自己。
那如果不加if判断，永远执行，会发生什么呢？事不宜迟……
作死的事就自己开个任务管理器或者活动监视器看看吧，不演示了……
递归的应用
斐波那契数列是一个很经典的递归应用。
int f(int n)
{
if (n == 1 || n == 2) return 1;
else return f(n-1) + f(n-2);
}
直接可以求到斐波那契数列的第 n 项。
斐波那契数列是啥就不用我说了吧……
但是，这个代码有一个最致命的问题：时间复杂度。小数据还好，大数据（不是）一旦遇到某个黑心出题人，给你搞个类似 65536 这样的数据，一秒完蛋。
不过也有解决办法。
数组优化递归
虽然说数组优化也会有极端情况，但是，数组优化已经能解决大部分情况了。
斐波那契数列可以这样优化：
vector
int f(int n)
{
if (n == 1 || n == 2) return 1;
else if (vec[n]) return vec[n];
else return vec[n] = f(n-1) + f(n-2);
}
这样能优化不少。
如果说 int 不够，那就用 long long ，再不行 _int128，再不行，就自己封装高精度结构体吧……
那这个时候又有彭于晏要问了：时间复杂度还是太长，怎么办？
如果你硬要让我用递归做，我也没有办法了。但是我可以用递推。
递推
递推本质上和动态规划一样，都是利用数组模拟过程，然后求出结果。
怎么实现呢？
首先，开个数组
#include
#define int long long
// 别问我为什么用这么奇怪的方式，int用惯了……
using namespace std;
int n;
int f[100005]; // 看题目要求，开这么大应该也够了。
signed main()
{
cin >> n;
f[1] = f[2] = 1; // 直接连等（不是）连续赋值
for (int i = 3; i <= n; i++)
{
// 核心代码，递推求结果
f[i] = f[i-1]+f[i-2];
}
cout << f[n] << endl;
return 0;
}
这是递推的应用
我愿称其为动态规划
其实动态规划比递推复杂太多了，各种方式，但都离不开数组。递推可以看作是基本动规。
递归和递推还有别的应用，刷题中找经验。（后面的深搜要用到递归，以后再说）
--End--