FANGT

递归函数深入

作者：

fangys

记忆化优化（Memoization）

问题背景

朴素递归往往存在重叠子问题（Overlapping Subproblems），导致同一状态被重复计算。以计算斐波那契数列 fib(n) 为例：

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

调用 fib(5) 时，fib(3) 被计算 2 次，fib(2) 被计算 3 次。当 n=40 时，重复计算量呈指数爆炸。

记忆化的核心思想

用空间换时间：将已经计算过的结果存储起来，当再次遇到相同输入时直接返回缓存结果，避免重复计算。

记忆化通常配合递归使用，属于自顶向下动态规划（Top‑Down DP）的一种实现方式。

实现方法

在 C++ 中常用数组作为缓存容器。

示例：记忆化斐波那契

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

long long memo[1000005] = {0, 1};
long long fib(int n) {
    if (n < 0) return -1;
    if (n == 0 || n == 1) return n;         
    if (memo[n] != 0) return memo[n];      
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    cout << fib(50) << endl;   // 瞬间得出结果，无重复计算
    return 0;
}

时间复杂度：O(n) （每个状态只计算一次）
空间复杂度：O(n) （递归栈深度 + 缓存数组）

什么时候使用记忆化

  • ✅ 问题具有重叠子问题（如斐波那契、爬楼梯、背包、区间DP）
  • ✅ 递归树中存在大量重复节点
  • ✅ 状态空间有限，可被缓存
  • ❌ 每个子问题只出现一次（如汉诺塔、二叉树遍历）→ 记忆化无收益
  • ❌ 状态空间过大（如全排列的指数级状态）→ 缓存不可行

常见递归题型

汉诺塔（Tower of Hanoi）

问题描述：三根柱子 A（源）、B（辅助）、C（目标），将 A 上的 n 个圆盘（大小不同）全部移动到 C，规则：

  • 每次移动一个圆盘
  • 大盘不能压在小盘上

递归思路：

  1. 将上面 n-1 个圆盘从 A 移到 B（借助 C）
  2. 将第 n 个圆盘从 A 直接移到 C
  3. 将 B 上的 n-1 个圆盘移到 C（借助 A）

代码：

#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << n << " from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);
    cout << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

时间复杂度：O(2ⁿ) （移动次数恰好为 2ⁿ – 1）
是否可记忆化：❌ 每个子问题状态 (n, from, to, aux) 组合不同，无重叠子问题。

爬楼梯（Climbing Stairs）

问题：一次可以爬 1 阶或 2 阶楼梯，求爬到第 n 阶有多少种不同方法。

递归关系：ways(n) = ways(n-1) + ways(n-2)，边界 ways(1)=1, ways(2)=2

朴素递归（重叠子问题严重）：

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

记忆化优化：

int memo[1000005] = {1, 1, 2};
int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (memo[n] != 0) return memo[n];
    memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return memo[n];
}

进阶变种：一次可以爬 1、2、3 阶 → 递推式变为 ways(n) = ways(n-1)+ways(n-2)+ways(n-3)

全排列（Permutations）

问题：给定一个字符串，返回所有可能的全排列。

递归思路：回溯法，依次确定每个位置的元素，使用 used 数组标记已选元素。

代码（无需记忆化，因为每个排列都是新状态）：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string s;          // 原始字符串（全局）
bool used[100];    // 标记字符是否用过（全局）
char cur[100];     // 当前排列（全局）
int n;             // 字符串长度（全局）

// 深度优先搜索，depth表示当前已经选了几个字符
void dfs(int depth) {
    if (depth == n) {
        cur[depth] = '\0';      // 加上字符串结束符
        cout << cur << endl;    // 输出一个排列
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            used[i] = true;
            cur[depth] = s[i];  // 选择第i个字符
            dfs(depth + 1);     // 递归下一层
            used[i] = false;    // 回溯，撤销选择
        }
    }
}

int main() {
    cin >> s;          // 输入字符串，例如 "abc"
    n = s.length();
    dfs(0);
    return 0;
}

C++自带全排列函数

  • std::next_permutation(begin, end)
    将当前序列变为字典序下一个更大的排列。如果存在下一个排列，返回 true；若已是最后一个排列（即降序），则变为第一个排列（升序）并返回 false。
  • std::prev_permutation(begin, end)
    变为字典序上一个更小的排列。
#include <iostream>
#include <algorithm>   // next_permutation
#include <string>
using namespace std;

int main() {
    string s = "abc";
    // 第一步：必须先排序，保证从第一个排列开始
    sort(s.begin(), s.end());
    
    do {
        cout << s << endl;   // 输出当前排列
    } while (next_permutation(s.begin(), s.end()));
    
    return 0;
}
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
do {
    for (int x : arr) cout << x << " ";
    cout << endl;
} while (next_permutation(arr, arr + n));