C++ 简单递推算法教程（0基础入门）

递推算法是一种通过已知的初始条件，利用特定的关系逐步推导出后续结果的算法。它的核心思想是"从已知推向未知"，非常适合解决有明显规律的问题。

什么是递推？

想象一下爬楼梯：如果你知道爬上第1级和第2级楼梯的方法，那么爬上第3级楼梯的方法就是爬上第1级后再爬2级，加上爬上第2级后再爬1级。这种从已知结果推出新结果的方式就是递推。

递推算法是编程中一种非常重要的思想，它通过已知的初始条件，利用特定的递推关系求出中间结果，进而得到最终答案。这种方法特别适合解决有明确规律的问题，代码简洁且效率高。

什么是递推算法？

递推算法的核心思想是：从已知条件出发，逐步推导出未知结果。它通常需要：

确定初始条件（基础情况）

找到递推关系式（如何从前面的结果推出后面的结果）

按照递推关系计算出最终答案

递推算法的优势

实现简单，代码可读性高

时间和空间效率通常较好

适合解决数列、组合计数、动态规划等多种问题

递推算法的基本步骤：

1. 确定初始条件（已知的起始值）
2. 找到递推关系（从已知值推出新值的公式）
3. 根据递推关系计算后续结果

示例1：计算斐波那契数列

斐波那契数列是典型的递推问题，数列规则如下：

• 第1项和第2项都是1
• 从第3项开始，每一项等于前两项之和

下面是实现代码：

#include <iostream>
using namespace std;

int main() {
    // 定义变量
    int n;              // 要计算的斐波那契数列的项数
    long long f[100];   // 用于存储斐波那契数列的数组，使用long long防止溢出
    
    // 输入要计算的项数
    cout << "请输入要计算的斐波那契数列的项数: ";
    cin >> n;
    
    // 1. 确定初始条件
    f[1] = 1;  // 第1项为1
    f[2] = 1;  // 第2项为1
    
    // 2. 利用递推关系计算后续项
    // 递推关系：f[i] = f[i-1] + f[i-2]
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    
    // 3. 输出结果
    cout << "斐波那契数列的前" << n << "项是: " << endl;
    for (int i = 1; i <= n; i++) {
        cout << f[i] << " ";
    }
    cout << endl;
    
    return 0;
}

代码解析：

1. 首先定义了变量和数组，数组用于存储计算结果
2. 设置初始条件：第1项和第2项都是1
3. 使用for循环和递推公式f[i] = f[i-1] + f[i-2]计算后续各项
4. 最后输出计算结果

示例2：计算阶乘

阶乘的递推关系也很简单：

• 0的阶乘是1（初始条件）
• n的阶乘 = n × (n-1)的阶乘（递推关系）

递推算法的优点：

1. 实现简单，容易理解
2. 效率高，时间复杂度通常为O(n)
3. 相比递归，不会出现栈溢出问题

练习：

尝试使用递推算法解决以下问题：

1. 有n级台阶，每次可以走1级或2级，求有多少种不同的走法
2. 计算1+2+3+...+n的和

提示：第一个问题的递推关系是f(n) = f(n-1) + f(n-2)，初始条件f(1)=1, f(2)=2。

通过这些例子，你应该对递推算法有了基本的了解。递推算法在解决数学问题、动态规划等领域有广泛应用，掌握它对于编程入门非常重要。