编程必备:深入了解C++递推

我还有很多故事，想在这里讲给你听！

C++递推是计算机解题的一种常用算法，是用若干步可重复的简单运算来描述复杂问题的方法。它的主要方面包括明确递推关系式、确定边界条件（初始值）以及通过递推求解得出结果。在递推问题模型里，每个数据项都与它前面的若干个数据项存在一定关联，这种关联通过“递推关系式”描述，求解时从初始的一个或若干数据项出发，借助递推关系式逐步推进，最终推导计算出想要的结果。递推的意义在于能够将复杂问题分解为简单的、可重复的步骤，通过已知条件逐步推出未知结果，有效降低问题的求解难度，提高编程效率，在解决各种实际问题和算法设计中发挥着重要作用 。

一、C++递推基本概念

（一）递推算法定义

递推算法是一种从初始值出发，按照固定运算规律逐次运算，直至求出问题解的方法。其本质是依据特定规律，逐步推导得出下一步结果。以斐波那契数列为例，数列前两项固定为1，从第三项起，每一项都等于前两项之和。用数学公式表示为：F(n) = F(n - 1) + F(n - 2) （n ≥ 3，F(1) = 1，F(2) = 1） 。从初始值 F(1) = 1、F(2) = 1 开始，依据此规律，就能依次算出后续各项数值。这种按部就班、依据规律推导的方式，正是递推算法的核心所在，它能将复杂问题拆解为一系列简单的、有规律可循的步骤，从而有效求解。

（二）递推与其他算法的区别

对比递推与递归算法，在程序形式上，递归表现为函数自身调用自身，程序结构相对复杂；递推则借助循环结构，按顺序逐次计算，形式较为直观。求解方向上，递归从问题最终目标出发，将复杂问题逐步化为简单问题，是逆向求解；递推从简单的初始值开始，一步步向前推进，是正向求解。对问题规模的要求方面，递归要求在计算前明确问题规模；递推在计算过程中确定规模即可。效率上，一般情况下，递推效率高于递归，因为递归存在大量函数调用开销。例如计算斐波那契数列第n 项，递归实现如下：

int fibonacciRecursive(int n) {

if (n <= 1) return n;

return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);

}

递推实现如下：

```cpp

int fibonacciIterative(int n) {

if (n <= 1) return n;

int a = 0, b = 1, result;

for (int i = 2; i <= n; ++i) {

result = a + b;

a = b;

b = result;

}

return result;

}

通过对比代码可直观看到，递推避免了递归的重复计算和函数调用开销，效率更高。

二、C++递推基础知识

（一）递推关系式的建立

建立递推关系式，关键在于细致分析问题，挖掘数据项间隐藏的内在联系。以斐波那契数列为例，该数列前两项固定为1，从第三项开始，每一项都是前两项之和。通过对数列各项的观察与分析，能够总结出递推关系式：F(n) = F(n - 1) + F(n - 2) （n ≥ 3，F(1) = 1，F(2) = 1）。此关系式清晰地展现了数列中相邻三项的数量关系，借助前两项，可顺利推出第三项。

再看猴子摘桃问题。猴子每天摘掉上一天剩下桃子的一半还多一个，到第N 天时，树上只剩两个桃子。从后往前分析，设第 i 天的桃子数为 f(i)，那么第 i - 1 天的桃子数 f(i - 1) 与 f(i) 的关系为：f(i - 1) = (f(i) + 1) * 2。这就是根据问题情境建立的递推关系式，它反映了相邻两天桃子数量的关联。

通过这些经典案例可知，建立递推关系式需深入理解问题本质，梳理数据项的变化规律，从而准确找出它们之间的数学关系，为问题求解奠定基础。

（二）边界条件的确定

边界条件在递推中至关重要，它是递推计算的起始点。若边界条件确定错误，后续的递推计算将失去正确根基，导致结果偏差。

以斐波那契数列为例，其边界条件为F(1) = 1，F(2) = 1。这是因为数列从这两项开始，依据特定规律生成后续各项。若没有这两个明确的初始值，递推关系式便无法启动计算。

在猴子摘桃问题中，边界条件是第N 天树上剩下两个桃子，即 f(N) = 2。这是整个递推过程的已知起点，基于此，利用递推关系式 f(i - 1) = (f(i) + 1) * 2，可逐步向前推算出之前每天的桃子数。

不同问题的边界条件需依据实际情况确定。要全面考虑问题的背景、初始状态等因素，确保边界条件既能准确反映问题的起始情况，又能为递推计算提供可靠的基础。

（三）递推的实现方式

在C++ 中，使用循环结构是实现递推的常见方式。循环结构能够依据递推关系式和边界条件，按顺序逐次计算，从而实现递推算法。

以计算斐波那契数列为例，代码实现如下：

int fibonacciIterative(int n) {

if (n <= 1) return n;

int a = 0, b = 1, result;

for (int i = 2; i <= n; ++i) {

result = a + b;

a = b;

b = result;

}

return result;

}

在这段代码中，首先根据边界条件处理n <= 1 的情况。然后，利用 for 循环从第 2 项开始，依据递推关系式 F(n) = F(n - 1) + F(n - 2)，通过不断更新变量 a、b 的值，计算出第 n 项的值。

这种实现方式借助循环结构，按照递推规律依次计算每一项，避免了递归算法中函数调用的开销，提高了计算效率。通过合理设置循环条件和递推计算逻辑，能够准确实现各种递推问题的求解。

三、C++递推的应用

（一）计数问题

在实际计数问题中，递推思想能将复杂的计数任务转化为简单的、有规律的计算。以走楼梯问题为例，假设有n 级台阶，每次只能跨上一级或两级，要计算走上第 n 级台阶的方法数。定义数组 f，f[i] 表示走到第 i 级台阶的方案数。

首先确定初始状态，f[1] = 1，因为走到第一级台阶只有一种方法；f[2] = 2，走到第二级台阶可以一次跨两级，或者分两次每次跨一级，共两种方法。接着找出递推规律，到达第i 级台阶的方式有两种，从第 i - 1 级跨一级上来，或者从第 i - 2 级跨两级上来，所以 f[i] = f[i - 1] + f[i - 2]。

再看铺地砖问题，有一个2 * n 的长方形地面，用 n 块 1 * 2 的地砖铺满，求铺设方法数。同样定义数组 f，f[i] 表示铺满 2 * i 长方形地面的方法数。f[1] = 1，只有一种铺法；f[2] = 2，有两种铺法。对于 2 * i 的地面，若最后一块地砖竖着铺，那么前面 2 * (i - 1) 的地面有 f[i - 1] 种铺法；若最后两块地砖横着铺，那么前面 2 * (i - 2) 的地面有 f[i - 2] 种铺法，所以 f[i] = f[i - 1] + f[i - 2]。

通过定义数组记录答案，找出递推规律，就能轻松编写代码实现计数问题的求解。

（二）序列问题

斐波那契数列是典型的递推序列，其特点是从第三项起，每一项都等于前两项之和。数学表达式为F(n) = F(n - 1) + F(n - 2) （n ≥ 3，F(1) = 1，F(2) = 1）。通过这个递推公式，从初始值 F(1) 和 F(2) 开始，就能依次计算出后续各项。在实际场景中，斐波那契数列可用于描述植物的生长规律、兔子繁殖等现象。

卡特兰数也是常见的序列，其前几项为1, 2, 5, 14, 42, … 。卡特兰数的特点与组合数学紧密相关，常用于解决如合法括号序列、凸多边形三角剖分等问题。以合法括号序列为例，设 f(n) 表示由 n 对括号组成的合法括号序列的数量。f(0) = 1，因为空序列是合法的。对于 n > 0 的情况，合法括号序列的最后一个字符一定是右括号，假设最终的括号序列为 A(B)，A 由 k 对括号组成，B 由 n - 1 - k 对括号组成，那么 f(n) = ∑ f(k) * f(n - 1 - k) （k 从 0 到 n - 1）。通过这个递推公式，可计算出不同 n 值对应的卡特兰数。

（三）排列组合问题

以错位排序问题为例，有n 个信封和 n 个信件，要求没有任何一个信件装入正确的信封，求方案数。设 f(n) 表示 n 个信件错位排列的方案数。首先确定初始值，f(1) = 0，因为只有一个信件时不存在错位排列；f(2) = 1，两个信件交换位置即可。

对于n 个信件，考虑第 1 个信件，它不能装入第 1 个信封，假设它装入了第 k 个信封（k ≠ 1）。此时第 k 个信件有两种情况：若第 k 个信件装入第 1 个信封，那么剩下的 n - 2 个信件就是一个 n - 2 个信件的错位排列问题，有 f(n - 2) 种方案；若第 k 个信件不装入第 1 个信封，此时可将第 1 个信封看作第 k 个信封，那么就相当于 n - 1 个信件的错位排列问题，有 f(n - 1) 种方案。而 k 有 n - 1 种选择，所以 f(n) = (n - 1) * (f(n - 1) + f(n - 2))。通过这个递推关系，就能计算出不同 n 值对应的错位排列方案数。

四、C++递推举例

（一）超级楼梯问题

题目描述：有一个超级楼梯共N 级，刚开始时你在第一级，若每次只能跨上一级或两级，要走上第 N 级，共有多少种走法？其中 N（1 <= N <= 105）。

输入输出要求：输入一个整数N，输出走到第 N 级的方案数，答案可能会很大，结果模上 2333333。

解题思路：到达第i 级台阶的方式有两种，从第 i - 1 级跨一级上来，或者从第 i - 2 级跨两级上来。所以递推关系式为 f[i] = f[i - 1] + f[i - 2]。边界条件为 f[1] = 1，因为走到第一级台阶只有一种方法；f[2] = 2，走到第二级台阶可以一次跨两级，或者分两次每次跨一级，共两种方法。

C++代码实现：