动态规划是解决多阶段决策问题的常用方法，而C++函数递归是实现动态规划思路的直观方式，很多动态规划问题的初始解法都可以通过递归来编写，理解二者的结合逻辑能帮助开发者更快掌握动态规划的核心思想。
C++函数递归基础
函数递归指的是函数直接或间接调用自身的编程技巧，递归需要包含两个部分：递归终止条件和递归调用逻辑。如果缺少终止条件，递归会无限执行直到栈溢出。
下面是一个简单的递归计算阶乘的示例，帮助理解递归的基本结构：
#include <iostream>
using namespace std;
// 递归计算n的阶乘
int factorial(int n) {
// 递归终止条件：0的阶乘是1
if (n == 0) {
return 1;
}
// 递归调用：n的阶乘等于n乘以n-1的阶乘
return n * factorial(n - 1);
}
int main() {
int num = 5;
cout << num << "的阶乘是：" << factorial(num) << endl;
return 0;
}动态规划中的递归应用逻辑
动态规划的核心思想是把复杂问题拆分成子问题，保存子问题的解避免重复计算，而递归刚好可以自然地拆分问题。很多动态规划问题的状态转移方程，直接对应递归的调用逻辑。
以经典的爬楼梯问题为例：假设你正在爬楼梯，需要n阶才能到达楼顶，每次你可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶。这个问题的状态转移方程是dp[n] = dp[n-1] + dp[n-2]，刚好可以用递归实现。
基础递归实现爬楼梯
直接按照状态转移方程写递归，代码如下：
#include <iostream>
using namespace std;
// 递归计算爬n阶楼梯的方法数
int climbStairs(int n) {
// 递归终止条件：1阶有1种方法，2阶有2种方法
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// 递归调用：n阶的方法数等于n-1阶加n-2阶的方法数
return climbStairs(n - 1) + climbStairs(n - 2);
}
int main() {
int n = 5;
cout << "爬" << n << "阶楼梯的方法数是：" << climbStairs(n) << endl;
return 0;
}递归在动态规划中的优化
上面的基础递归实现存在重复计算的问题，比如计算climbStairs(5)的时候会计算climbStairs(4)和climbStairs(3)，而计算climbStairs(4)又会计算climbStairs(3)，重复计算会大幅降低效率。动态规划中常用记忆化递归解决这个问题，也就是把已经计算过的子问题结果保存下来，下次遇到直接返回。
记忆化递归优化爬楼梯
用数组保存已经计算过的结果，优化后的代码如下：
#include <iostream>
#include <vector>
using namespace std;
// 记忆化数组，初始化为-1表示未计算
vector<int> memo;
int climbStairs(int n) {
// 递归终止条件
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// 如果已经计算过，直接返回结果
if (memo[n] != -1) {
return memo[n];
}
// 计算并保存结果
memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
return memo[n];
}
int main() {
int n = 5;
// 初始化记忆化数组，大小为n+1，全部赋值为-1
memo.resize(n + 1, -1);
cout << "爬" << n << "阶楼梯的方法数是：" << climbStairs(n) << endl;
return 0;
}递归实现动态规划的注意事项
使用递归实现动态规划的时候，需要注意几个问题：首先是递归深度，如果问题规模过大，递归调用层数太多会导致栈溢出，这时候可以考虑改用迭代方式实现动态规划；其次是终止条件要写准确，避免遗漏边界情况；最后是记忆化的存储结构要选择合适的，比如用数组、哈希表来保存子问题的解，根据问题的状态范围决定。
另外，有些动态规划问题的递归写法可能比迭代更直观，比如背包问题的递归实现，能更清晰地体现状态转移的逻辑，开发者可以根据具体问题选择合适的方式，递归和迭代都是实现动态规划的有效手段，核心是理解问题的拆分和子问题解的复用。