递归算法模板

#include <bits/stdc++.h>
using namespace std;

// 阶乘
long long fact(int n) {
    if (n <= 1) return 1;     // 终止条件
    return n * fact(n - 1);   // 递推关系
}

// 斐波那契（带记忆化）
long long memo[60];
long long fib(int n) {
    if (n <= 2) return 1;
    if (memo[n]) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// 汉诺塔
void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        cout << from << " -> " << to << endl;
        return;
    }
    hanoi(n-1, from, to, mid);
    cout << from << " -> " << to << endl;
    hanoi(n-1, mid, from, to);
}

// 全排列
void permute(vector<int> &a, int start) {
    if (start == a.size()) {
        for (int x : a) cout << x << " ";
        cout << endl;
        return;
    }
    for (int i = start; i < a.size(); i++) {
        swap(a[start], a[i]);
        permute(a, start + 1);
        swap(a[start], a[i]);  // 回溯
    }
}

int main() {
    cout << fact(10) << endl;  // 3628800
    cout << fib(50) << endl;   // 12586269025
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

📖 要点说明

• 递归三要素：终止条件、递推关系、返回值
• 记忆化避免重复计算，fib 从 O(2^n) 降到 O(n)
• 回溯 = 递归+撤销选择

⚠️ 常见错误

• 忘写终止条件导致栈溢出
• 递归深度太深（如 fib(50) 不加记忆化）
• 回溯忘撤销选择