递推求解算法详解

1. 递推算法基本概念

递推算法是一种通过已知条件，利用特定关系推导出未知结果的数学方法。在计算机编程中，递推通常通过循环实现，从初始状态开始，逐步计算出后续状态。

1.1 递推与递归的区别

特征	递推	递归
实现方式	循环	函数调用自身
效率	高	低（存在重复计算）
内存使用	少	多（栈空间）
适用场景	线性问题	树形结构问题

2. 经典递推问题分析

2.1 年龄问题

问题描述：5个人坐在一起，第5个人说比第4个人大2岁，第4个人说比第3个人大2岁，以此类推，第1个人10岁。求第5个人的年龄。

递推关系：

f(1) = 10
f(n) = f(n-1) + 2 (n ≥ 2)

代码实现：

#include <iostream>
using namespace std;

int age(int n) {
    if (n == 1) return 10;
    return age(n-1) + 2;
}

// 更高效的迭代实现
int age_iterative(int n) {
    int result = 10;
    for (int i = 2; i <= n; i++) {
        result += 2;
    }
    return result;
}

int main() {
    int n = 5;
    cout << "第" << n << "个人的年龄是：" << age_iterative(n) << endl;
    return 0;
}

2.2 斐波那契数列

问题描述：斐波那契数列由以下递推关系定义：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

代码实现：

#include <iostream>
using namespace std;

// 递归实现（不推荐，效率低）
long long fibonacci_recursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
}

// 迭代实现（推荐）
long long fibonacci_iterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// 数组实现（便于理解）
long long fibonacci_array(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    long long fib[n+1];
    fib[0] = 0;
    fib[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

int main() {
    int n = 10;
    cout << "F(" << n << ") = " << fibonacci_iterative(n) << endl;
    return 0;
}

2.3 平面分割问题

2.3.1 直线分割平面

问题描述：n条直线最多能将平面分割成多少区域？

递推关系：

f(1) = 2
f(n) = f(n-1) + n

推导过程：

• 第n条直线与前面n-1条直线最多有n-1个交点
• 这些交点把第n条直线分成n段
• 每段把原来的一个区域分成两个，因此增加n个区域

代码实现：

#include <iostream>
using namespace std;

int line_partition(int n) {
    if (n == 1) return 2;
    return line_partition(n-1) + n;
}

// 直接公式：f(n) = n(n+1)/2 + 1
int line_partition_formula(int n) {
    return n * (n + 1) / 2 + 1;
}

int main() {
    int n = 5;
    cout << n << "条直线最多分割平面：" << line_partition(n) << "个区域" << endl;
    return 0;
}

2.3.2 折线分割平面

问题描述：n条折线最多能将平面分割成多少区域？

递推关系：

f(1) = 2
f(n) = f(n-1) + 4(n-1) + 1

推导过程：

• 每条折线相当于两条直线，但少了一个区域
• 第n条折线最多与前面n-1条折线有4(n-1)个交点
• 被分成4(n-1)+1段，每段增加一个区域

代码实现：

#include <iostream>
using namespace std;

int fold_line_partition(int n) {
    if (n == 1) return 2;
    return fold_line_partition(n-1) + 4*(n-1) + 1;
}

int main() {
    int n = 3;
    cout << n << "条折线最多分割平面：" << fold_line_partition(n) << "个区域" << endl;
    return 0;
}

2.4 骨牌铺放问题

2.4.1 2×n骨牌铺放

问题描述：用1×2骨牌铺满2×n的方格，有多少种铺法？

递推关系：

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

代码实现：

#include <iostream>
using namespace std;

long long domino_2n(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    long long a = 1, b = 2, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 5;
    cout << "2×" << n << "方格铺法数量：" << domino_2n(n) << endl;
    return 0;
}

2.4.2 1×n骨牌铺放（多种骨牌）

问题描述：用1×1、1×2、1×3三种骨牌铺满1×n的方格，有多少种铺法？

递推关系：

f(1) = 1
f(2) = 2
f(3) = 4
f(n) = f(n-1) + f(n-2) + f(n-3)

代码实现：

#include <iostream>
using namespace std;

long long domino_1n(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    
    long long a = 1, b = 2, c = 4, d;
    for (int i = 4; i <= n; i++) {
        d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return c;
}

int main() {
    int n = 5;
    cout << "1×" << n << "方格铺法数量：" << domino_1n(n) << endl;
    return 0;
}

2.5 排队问题（女生不能单独站）

问题描述：n个人排队，女生不能单独站（有女生时必须有其他女生相邻），求合法排队方案数。

递推关系：

f(n) = f(n-1) + f(n-4) + f(n-2)

二维状态递推： 设：

• f0(n)：以男生结尾的合法队列数
• f1(n)：以女生结尾的合法队列数

则：

f0(n) = f0(n-1) + f1(n-1)
f1(n) = f0(n-2) + f1(n-2)
f(n) = f0(n) + f1(n)

代码实现：

#include <iostream>
using namespace std;

long long queue_arrangement(int n) {
    if (n == 1) return 1;  // 只有男生
    if (n == 2) return 2;  // 男男、女女
    
    long long f0 = 1, f1 = 1;  // n=1时
    long long new_f0, new_f1;
    
    for (int i = 2; i <= n; i++) {
        new_f0 = f0 + f1;      // 以男生结尾：前面任意合法队列+男生
        new_f1 = f0;           // 以女生结尾：前面必须以男生结尾+女生（形成男女女）
        f0 = new_f0;
        f1 = new_f1;
    }
    
    return f0 + f1;
}

int main() {
    int n = 4;
    cout << n << "个人合法排队方案数：" << queue_arrangement(n) << endl;
    return 0;
}

3. 卡特兰数（Catalan Number）

3.1 卡特兰数的应用

卡特兰数出现在许多组合计数问题中：

• 凸多边形的三角形划分
• 括号序列
• 出栈序列
• 二叉树形态
• 不相交的弦连接

3.2 卡特兰数的递推公式

C(0) = 1
C(n) = Σ[C(i) * C(n-1-i)]，i从0到n-1

3.3 代码实现

#include <iostream>
#include <vector>
using namespace std;

long long catalan(int n) {
    vector<long long> C(n+1, 0);
    C[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            C[i] += C[j] * C[i-1-j];
        }
    }
    
    return C[n];
}

// 直接公式：C(n) = C(2n,n) / (n+1)
long long catalan_formula(int n) {
    long long result = 1;
    // 计算C(2n,n)
    for (int i = 1; i <= n; i++) {
        result = result * (2*n - i + 1) / i;
    }
    return result / (n+1);
}

int main() {
    int n = 5;
    cout << "Catalan(" << n << ") = " << catalan(n) << endl;
    return 0;
}

4. 递推问题分类与解题技巧

4.1 递推问题分类

1. 一维递推：当前状态只与前面有限个状态有关

   • 斐波那契数列：f(n) = f(n-1) + f(n-2)
   • 骨牌铺放问题

2. 二维递推：使用多个状态变量

   • 排队问题：使用f0(n)和f1(n)

3. 卷积型递推：当前状态是前面状态的加权和

   • 卡特兰数：C(n) = Σ[C(i)*C(n-1-i)]

4.2 解题技巧

1. 寻找初始状态：确定最小规模问题的解
2. 分析状态转移：找出当前状态与之前状态的关系
3. 选择实现方式：
   • 小规模：递归（加记忆化）
   • 大规模：迭代（数组或变量滚动）
4. 优化空间：使用变量滚动减少空间复杂度

4.3 避免递归陷阱

// 错误的递归实现（指数时间复杂度）
int fibonacci_bad(int n) {
    if (n <= 1) return n;
    return fibonacci_bad(n-1) + fibonacci_bad(n-2);
}

// 正确的记忆化递归
#include <unordered_map>
unordered_map<int, long long> memo;

long long fibonacci_memo(int n) {
    if (n <= 1) return n;
    if (memo.find(n) != memo.end()) return memo[n];
    
    memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2);
    return memo[n];
}

5. 实战建议

1. 从简单情况开始：先分析n=1,2,3的情况
2. 寻找规律：观察前后项之间的关系
3. 验证公式：用小数据验证递推公式的正确性
4. 注意边界：处理好n=0,1等边界情况
5. 优化实现：根据数据规模选择合适的实现方式

通过系统学习递推算法，你能够解决许多经典的计数问题，并为学习更复杂的动态规划算法打下坚实基础。递推思想在编程竞赛和实际开发中都有广泛应用，是每个程序员应该掌握的重要技能。