基础概念

递归，即调用函数自身。本质上是将问题拆解成更小规模的相同问题。

简单优化思路（==记忆化搜索==）：如果有重复计算，将结果保存下来

递归方法：

  • 确定问题
  • 解决基准问题
  • 拆解问题

示例

斐波那契数列（Fibonacci）

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

当出现重复问题时数据会成指数型增长,子问题会被重复计算多次.

可以在计算时将计算过的保存下来,并在计算时再判断是否计算过,用来优化性能

1
2
3
4
5
6
7
8
vector<int> saved(n,-1);
int fib(int n){
    if(n <= 2) return 1;
    if(saved[n] == -1){
        saved[n] = fib(n-1) + fib(n-2);
    }
    return saved[n];
}

汉诺塔(honai)

1
2
3
4
5
6
7
8
9
void hanoi(int n, char F, char A, char T){
    if(n == 1){
        printf("move %d from %c to %c\n", n, F, T);
        return;
    }
    hanoi(n - 1, F, T, A);
    printf("move %d from %c to %c\n", n, F, T);
    hanoi(n - 1, A, F, T);
}