递归法

#include <iostream>
using namespace std;

int sum_digits(int n) {
    // 终止条件：个位数直接返回
    if (n < 10) return n;

// 递归：个位 + 去掉个位后的数字之和
    return n % 10 + sum_digits(n / 10);
}

int main() {
    int n; cin >> n;
    cout << sum_digits(n) << endl;
    return 0;
}

#include <iostream>
using namespace std;

int a[] = {2,5,8,12,16,23,38,56,72,91};

int bsearch(int l, int r, int target) {
    // 终止条件1：范围无效，没找到
    if (l > r) return -1;

int mid = l + (r - l) / 2;

// 终止条件2：找到了
    if (a[mid] == target) return mid;

// 递归：在左半或右半继续找
    if (target < a[mid])
        return bsearch(l, mid - 1, target);
    else
        return bsearch(mid + 1, r, target);
}

int main() {
    cout << bsearch(0, 9, 23) << endl;  // 输出 5
    cout << bsearch(0, 9, 10) << endl;  // 输出 -1
    return 0;
}

#include <iostream>
using namespace std;

long long memo[105];
bool computed[105] = {};  // 记录是否已计算

long long f(int n) {
    if (n == 1) return 1;
    if (computed[n]) return memo[n];

computed[n] = true;
    memo[n] = f(n-1) + f(n/2) + n;
    return memo[n];
}

int main() {
    cout << f(100) << endl;
    return 0;
}

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

string reverse_str(string s) {
    // 终止条件：空串或单字符
    if (s.length() <= 1) return s;

// 递归：最后一个字符 + 反转剩余部分
    return s[s.length()-1] + reverse_str(s.substr(0, s.length()-1));
}

int main() {
    string s; cin >> s;
    cout << reverse_str(s) << endl;
    return 0;
}

#include <iostream>
using namespace std;

int n;
int perm[10];
bool used[10] = {};

void dfs(int pos) {
    // 终止条件：已经填完 n 个位置
    if (pos == n) {
        for(int i=0;i<n;i++) cout << perm[i];
        cout << " ";
        return;
    }

// 尝试在每个位置填入 1~n 中未使用的数字
    for(int i=1;i<=n;i++) {
        if(!used[i]) {
            used[i] = true;
            perm[pos] = i;
            dfs(pos + 1);      // 递归填下一个位置
            used[i] = false;  // 回溯！
        }
    }
}

int main() {
    cin >> n;
    dfs(0);
    cout << endl;
    return 0;
}

#include <iostream>
using namespace std;

long long fast_pow(long long a, long long n, long long p) {
    // 终止条件
    if (n == 0) return 1;

// 递归计算 a^(n/2)
    long long half = fast_pow(a, n / 2, p);
    half = half * half % p;

// 如果 n 是奇数，多乘一个 a
    if (n % 2 == 1)
        half = half * (a % p) % p;

return half;
}

int main() {
    long long a, n, p;
    cin >> a >> n >> p;
    cout << fast_pow(a, n, p) << endl;
    return 0;
}

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

int a[105][105];
int memo[105][105];
bool comp[105][105] = {};
int n;

int dfs(int r, int c) {
    // 终止条件：到达最后一行
    if (r == n - 1) return a[r][c];

// 查缓存
    if (comp[r][c]) return memo[r][c];

// 递归：取左下和右下的最大值 + 当前位置
    comp[r][c] = true;
    memo[r][c] = a[r][c] + max(dfs(r+1, c), dfs(r+1, c+1));
    return memo[r][c];
}

int main() {
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin >> a[i][j];
    cout << dfs(0, 0) << endl;
    return 0;
}