————————————————————————————————————————————————————
————————————————————————————————————————————————————方奎
一：递推
特点：
* 时间效率高（无函数调用开销）
* 空间可优化（通常只需存储少量中间结果）
* 逻辑直观，适合有明确递推关系的问题
1. 典型问题：斐波那契数列
问题：求第 n 个斐波那契数 （F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)）（F (0)=0, F (1)=1, F (n)=F (n-1)+F (n-2)）（F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)）
递推公式：
F(n)={0n=01n=1F(n−1)+F(n−2)n≥2 F(n) = \begin{cases} 0 &n=0\\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq2 \end{cases} F(n)=⎩⎨⎧ 01F(n−1)+F(n−2) n=0n=1n≥2
代码模板：
2. 典型问题：爬楼梯
问题：一次可爬1或2阶，求爬n阶的方法数
递推公式：
f(n)={1n=12n=2f(n−1)+f(n−2)n≥3 f(n) = \begin{cases} 1 &n=1\\ 2 & n=2 \\ f(n-1)+f(n-2) & n\ge3 \end{cases} f(n)=⎩⎨⎧ 12f(n−1)+f(n−2) n=1n=2n≥3
代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、递归
特点：
* 代码简洁，接近数学定义
* 可能存在重复计算（需优化）
* 受栈深度限制（易栈溢出）
1. 典型问题：阶乘
问题：求n的阶乘 （n!=n×(n−1)×…×1，0!=1）（n! = n×(n-1)×…×1，0! = 1）（n!=n×(n−1)×…×1，0!=1）
递归公式：
n!={1n=0n×(n−1)!n≥1 n! = \begin{cases} 1 &n=0\\ n\times(n-1)! & n\ge1 \end{cases} n!={1n×(n−1)! n=0n≥1
代码：
2. 典型问题：斐波那契数列（递归版）
递归公式：同递推版（但计算方式不同）
F(n)={0n=01n=1F(n−1)+F(n−2)n≥2 F(n) = \begin{cases} 0 &n=0\\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq2 \end{cases} F(n)=⎩⎨⎧ 01F(n−1)+F(n−2) n=0n=1n≥2
问题：直接递归会重复计算（如F(5)需计算F(4)和F(3)，F(4)又需计算F(3)和F(2)，F(3)被重复计算）。
优化：用记忆化搜索（存储已计算结果）。
记忆化递归代码模板：
3. 典型问题：汉诺塔
问题：将n个盘子从A柱移到C柱，中间用B柱过渡，每次只能移1个盘，且大盘不能放小盘上。
递归思路：
1. 将n-1个盘从A→B（借助C）
2. 将第n个盘从A→C
3. 将n-1个盘从B→C（借助A）
递归公式：移动n个盘的步数为 T(n)=2×T(n−1)+1T(n) = 2 \times T(n-1) + 1T(n)=2×T(n−1)+1，且 T(1)=1T(1) = 1T(1)=1，最终 T(n)=2n−1T(n) = 2^n - 1T(n)=2n−1。
代码模板：
三、递推与递归的对比
维度 递推（迭代） 递归 思维方式 自底向上（从小问题推大问题） 自顶向下（分解大问题为小问题） 时间效率 高（无函数调用开销） 较低（有调用栈开销，可能重复计算） 空间效率 可优化（O(1)或O(n)） 通常O(n)（递归栈深度） 适用场景 递推关系明确、规模较大的问题 问题可分解为同类子问题（如树、分治）
递推适合追求效率的场景，递归适合逻辑简洁性优先的场景（复杂问题可用记忆化优化）。实际开发中需根据问题特性选择。
