#创作计划# 递推与递归（请输入WenB

Lexora_

2025-07-30 15:45:33

发布于：浙江

14阅读

0回复

0点赞

————————————————————————————————————————————————————

————————————————————————————————————————————————————方奎

一：递推

 定义：从已知的初始条件出发，通过迭代计算逐步推出后续结果的方法。核心是 “自底向上”，先解决小问题，再用小问题的解构建大问题的解。

特点：

时间效率高（无函数调用开销）
空间可优化（通常只需存储少量中间结果）
逻辑直观，适合有明确递推关系的问题

典型问题：斐波那契数列

问题：求第 n 个斐波那契数 $（F (0)=0, F (1)=1, F (n)=F (n-1)+F (n-2)）$

递推公式：

$F(n) = \begin{cases} 0 &n=0\\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq2 \end{cases}$

代码模板：

// 请输入文本

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n; // 初始条件
    int a = 0, b = 1, res; // 用变量存储中间结果（空间优化）
    for (int i = 2; i <= n; i++) {
        res = a + b;
        a = b;      // 迭代更新：a变为前一个b
        b = res;    // b变为当前结果
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl; // 示例：n=5 → 5
    return 0;
}

典型问题：爬楼梯

问题：一次可爬1或2阶，求爬n阶的方法数

递推公式：

$f(n) = \begin{cases} 1 &n=1\\ 2 & n=2 \\ f(n-1)+f(n-2) & n\ge3 \end{cases}$

代码：

#include <iostream>
using namespace std;

int pa(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int prev_prev = 1, prev = 2, curr; // 存储f(n-2)和f(n-1)
    for (int i = 3; i <= n; i++) {
        curr = prev_prev + prev;
        prev_prev = prev;
        prev = curr;
    }
    return curr;
}

int main() {
    int n;
    cin >> n;
    cout << pa(n) << endl; // 示例：n=3 → 3
    return 0;
}

二、递归

定义：函数通过调用自身解决问题的方法。核心是“自顶向下”，将大问题分解为与原问题结构相同的小问题，直到达到基线条件（停止递归的条件）。

特点：

代码简洁，接近数学定义
可能存在重复计算（需优化）
受栈深度限制（易栈溢出）

典型问题：阶乘

问题：求n的阶乘 $（n! = n×(n-1)×…×1，0! = 1）$

递归公式：

$n! = \begin{cases} 1 &n=0\\ n\times(n-1)! & n\ge1 \end{cases}$

代码：

#include <iostream>
using namespace std;

// 递归计算阶乘
int jiecheng(int n) {
    if (n == 0) return 1; // 基线条件：0! = 1
    return n * jiecheng(n - 1); // 递归调用：n! = n×(n-1)!
}

int main() {
    int n;
    cin >> n;
    cout << jiecheng(n) << endl; // 示例：n=5 → 120
    return 0;
}

典型问题：斐波那契数列（递归版）

递归公式：同递推版（但计算方式不同）

$F(n) = \begin{cases} 0 &n=0\\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq2 \end{cases}$

问题：直接递归会重复计算（如F(5)需计算F(4)和F(3)，F(4)又需计算F(3)和F(2)，F(3)被重复计算）。

优化：用记忆化搜索（存储已计算结果）。

记忆化递归代码模板：

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

vector<int> memo; // 存储已计算的F(n)

int fib(int n) {
    if (n <= 1) return n; // 基线条件
    if (memo[n] != -1) return memo[n]; // 若已计算，直接返回
    // 递归计算并存储结果
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int fibonacci(int n) {
    memo.resize(n + 1, -1); // 初始化记忆数组
    return fib(n);
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl; // 示例：n=10 → 55
    return 0;
}

典型问题：汉诺塔

问题：将n个盘子从A柱移到C柱，中间用B柱过渡，每次只能移1个盘，且大盘不能放小盘上。

递归思路：

将n-1个盘从A→B（借助C）
将第n个盘从A→C
将n-1个盘从B→C（借助A）

递归公式：移动n个盘的步数为 $T(n) = 2 \times T(n-1) + 1$ ，且 $T(1) = 1$ ，最终 $T(n) = 2^n - 1$ 。

代码模板：

#include <iostream>
using namespace std;

// 将n个盘子从from柱移到to柱，借助aux柱
void hanoi(int n, char from, char aux, char to) {
    if (n == 1) { // 基线条件：1个盘直接移
        cout << to << endl;
        return;
    }
    // 步骤1：n-1个盘从from→aux（借助to）
    hanoi(n - 1, from, to, aux);
    // 步骤2：第n个盘从from→to
    cout << to << endl;
    // 步骤3：n-1个盘从aux→to（借助from）
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C'); // 示例：n=2 → 3步
    return 0;
}

三、递推与递归的对比

维度	递推（迭代）	递归
思维方式	自底向上（从小问题推大问题）	自顶向下（分解大问题为小问题）
时间效率	高（无函数调用开销）	较低（有调用栈开销，可能重复计算）
空间效率	可优化（O(1)或O(n)）	通常O(n)（递归栈深度）
适用场景	递推关系明确、规模较大的问题	问题可分解为同类子问题（如树、分治）