递推算法

George222 Lv3

2024-08-28 09:51:26 2024-08-28 09:51:26 创建 2024-09-12 17:41:19 2024-09-12 17:41:19 更新

递归与递推

递推算法是一种简单的算法，递推通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。

相对于递归算法，递推算法免除了数据进出栈的过程，不需要函数不断的向边界值靠拢，而直接从边界出发，直到求出函数值。

比如阶乘函数：。

递归中的表现是这样的：

-> -> -> -> -> -> -> ->

而递推则是：

-> -> -> ->

很明显，递推效率更高。

斐波那契数列，求第个值。

跟着代码讲：

// 设 f[i] 为斐波那契数列的第 n 项。
f[1] = 1;
f[2] = 1;
for (int i = 3; i <= n; i++)
{
	f[i] = f[i - 1] + f[i - 2];
}
cout << f[n];

看的处理，递推是线性算法，时间复杂度明显更低。