递推与递归算法的典型实现与代码优化
一、多状态同步迭代
在处理具有多个相互依赖变量的递推问题时，直接使用连续赋值容易导致状态覆盖错误。通过引入临时缓存或显式的状态转移步骤，可以确保每一轮迭代的输入值均来自上一轮的正确结果。该模型常用于模拟复杂系统的状态演进。
#include <iostream>
int main() {
int iterations;
std::cin >> iterations;
long long state_a = 1, state_b = 0, state_c = 0;
for (int k = 0; k < iterations; ++k) {
long long next_a = state_a + state_b;
long long next_b = state_c;
long long next_c = next_a + state_c;
state_a = next_a;
state_b = next_b;
state_c = next_c;
}
std::cout << state_a << std::endl;
return 0;
}二、斐波那契数列的线性递推
斐波那契型数列是递推算法的基础原型。利用数组存储中间计算结果，可以将时间复杂度从指数级优化至线性级。此处采用定长容器进行状态缓存，直接输出指定位置的序列值。
#include <iostream>
#include <vector>
int main() {
int limit;
std::cin >> limit;
std::vector<long long> fib(limit + 1, 0);
fib[1] = fib[2] = 1;
for (int idx = 3; idx <= limit; ++idx) {
fib[idx] = fib[idx - 1] + fib[idx - 2];
}
std::cout << fib[limit] << std::endl;
return 0;
}三、累加型递推关系
当递推公式呈现为 $a_i = a_{i-1} + i$ 形式时，实质上是在构建等差数列的前缀和。该逻辑可直接转化为单向累加循环，无需额外开辟数组空间，实现空间复杂度的常数级优化。
#include <iostream>
int main() {
int upper_bound;
std::cin >> upper_bound;
long long accumulator = 2;
for (int step = 2; step <= upper_bound; ++step) {
accumulator += step;
}
std::cout << accumulator << std::endl;
return 0;
}四、互质判定与辗转相除法
欧几里得算法通过不断取模替换较大值，快速收敛至最大公约数。若最终公约数为1，则两数互质。该实现通过迭代更新避免了递归调用的栈开销。
#include <iostream>
int main() {
long long x, y;
std::cin >> x >> y;
while (y != 0) {
long long remainder = x % y;
x = y;
y = remainder;
}
if (x == 1) std::cout << "Yes" << std::endl;
else std::cout << "No" << std::endl;
return 0;
}五、汉诺塔问题的分治递归
汉诺塔是递归思想的经典应用场景。将 $n$ 个圆盘从起始柱移动至目标柱，可拆解为：先将 $n-1$ 个圆盘移至辅助柱，移动底部最大圆盘，再将 $n-1$ 个圆盘从辅助柱移至目标柱。边界条件为 $n=0$ 时直接返回。
#include <iostream>
using namespace std;
void move_disks(int count, char source, char aux, char target) {
if (count <= 0) return;
move_disks(count - 1, source, target, aux);
cout << source << "->" << count << "->" << target << endl;
move_disks(count - 1, aux, source, target);
}
int main() {
int total_disks;
char rod_a, rod_b, rod_c;
cin >> total_disks >> rod_a >> rod_b >> rod_c;
move_disks(total_disks, rod_a, rod_b, rod_c);
return 0;
}六、受限步长的路径计数
在步长受限的移动问题中，到达第 $i$ 个位置的方案数等于从合法前驱位置转移而来的方案之和。通过预设初始边界条件，即可利用状态转移方程完成动态规划填表。
#include <iostream>
int main() {
int target;
std::cin >> target;
long long dp[1005] = {0};
dp[2] = 1;
dp[3] = 1;
for (int pos = 4; pos <= target; ++pos) {
dp[pos] = dp[pos - 2] + dp[pos - 3];
}
std::cout << dp[target] << std::endl;
return 0;
}七、逆向思维倒推模型
对于已知最终状态反推初始状态的题目，正向计算往往复杂，而从终点向起点逆向还原则逻辑清晰。每一步执行逆运算，即可高效还原原始数值。
#include <iostream>
int main() {
int steps;
std::cin >> steps;
long long value = 1;
for (int i = 1; i < steps; ++i) {
value = (value + 1) << 1;
}
std::cout << value << std::endl;
return 0;
}八、阶梯攀登方案统计
每次允许攀登1阶或2阶楼梯时，到达第 $n$ 阶的方案数符合斐波那契数列变体。通过数组记忆化中间结果，避免重复子问题的冗余计算。
#include <iostream>
int main() {
int floors;
std::cin >> floors;
long long ways[1005] = {0};
ways[1] = 1;
ways[2] = 2;
for (int i = 3; i <= floors; ++i) {
ways[i] = ways[i - 1] + ways[i - 2];
}
std::cout << ways[floors] << std::endl;
return 0;
}九、最大公约数直接输出
与互质判定类似，若仅需获取两数的最大公约数，可直接在循环结束后输出收敛值。该实现采用模运算迭代，具备对数级时间复杂度。
#include <iostream>
int main() {
long long num_a, num_b;
std::cin >> num_a >> num_b;
while (num_b != 0) {
long long temp = num_a % num_b;
num_a = num_b;
num_b = temp;
}
std::cout << num_a << std::endl;
return 0;
}十、带参依赖的动态规划
当递推关系涉及外部参数且序列间存在交叉引用时，需维护多个状态数组并严格控制访问边界。通过预先填充基准区间，并按序更新衍生序列，可处理复杂的参数化递推逻辑。
#include <iostream>
#include <vector>
int main() {
int threshold, multiplier, range;
std::cin >> threshold >> multiplier >> range;
std::vector<long long> seq_a(range + 1, 0);
std::vector<long long> seq_b(range + 1, 0);
for (int i = 0; i < threshold; ++i) seq_a[i] = 1;
for (int i = threshold; i <= range; ++i) {
seq_a[i] = seq_a[i - 1] + seq_b[i - 2];
seq_b[i] = seq_a[i - threshold] * multiplier;
}
std::cout << seq_a[range] << std::endl;
return 0;
}