L4_05 递推算法

一、递推算法基本思想

1.1 概念

递推算法是一种通过已知条件，利用特定关系逐步推导出未知结果的算法。

1.2 特点

• 从已知条件出发，逐步推导
• 每一步的结果依赖于前面的结果
• 适合解决有规律的问题

1.3 分类

• 顺推：从初始条件出发，逐步向后推导
• 逆推：从最终结果出发，逐步向前推导

---

二、递推关系式推导

2.1 斐波那契数列

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)  (n >= 3)

2.2 阶乘

F(0) = 1
F(n) = n * F(n-1)  (n >= 1)

2.3 等差数列

a(1) = a1
a(n) = a(n-1) + d  (d为公差)

---

三、顺推示例

3.1 斐波那契数列（顺推）

#include <iostream>
using namespace std;

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

int main() {
    cout << "第10个斐波那契数: " << fibonacci(10) << endl;
    return 0;
}

3.2 计算阶乘

#include <iostream>
using namespace std;

long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    cout << "5! = " << factorial(5) << endl;
    return 0;
}

---

四、逆推示例

4.1 猴子吃桃问题

猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。
第二天早上又将剩下的桃子吃掉一半，又多吃了一个。
以后每天早上都吃前一天剩下的一半零一个。
到第10天早上想再吃时，只剩下一个桃子了。
求第一天共摘了多少桃子？

递推公式：
f(n) = (f(n+1) + 1) * 2
f(10) = 1

#include <iostream>
using namespace std;

int main() {
    int peaches = 1;  // 第10天剩下的桃子
    for (int i = 9; i >= 1; i--) {
        peaches = (peaches + 1) * 2;
    }
    cout << "第一天摘了: " << peaches << "个桃子" << endl;
    return 0;
}

---

五、递推算法的应用

5.1 爬楼梯问题

一个人爬楼梯，每次可以爬1级或2级台阶，求爬到n级台阶有多少种方法。

递推公式：
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

#include <iostream>
using namespace std;

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

int main() {
    cout << "爬到第5级台阶有" << climbStairs(5) << "种方法" << endl;
    return 0;
}

5.2 杨辉三角

#include <iostream>
using namespace std;

int main() {
    int n = 5;
    int triangle[10][10] = {0};
    
    // 初始化边界
    for (int i = 0; i < n; i++) {
        triangle[i][0] = 1;
        triangle[i][i] = 1;
    }
    
    // 递推计算
    for (int i = 2; i < n; i++) {
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    // 输出杨辉三角
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << triangle[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

---

六、示例程序

#include <iostream>
using namespace std;

// 递推求解等差数列第n项
int arithmeticSequence(int a1, int d, int n) {
    return a1 + (n - 1) * d;
}

// 递推求解等比数列第n项
double geometricSequence(double a1, double r, int n) {
    double result = a1;
    for (int i = 2; i <= n; i++) {
        result *= r;
    }
    return result;
}

int main() {
    // 等差数列: 1, 3, 5, 7, 9...
    cout << "等差数列第10项: " << arithmeticSequence(1, 2, 10) << endl;
    
    // 等比数列: 2, 6, 18, 54...
    cout << "等比数列第5项: " << geometricSequence(2, 3, 5) << endl;
    
    return 0;
}