递归的三个场景

一、1到n的和

public int sum(int n) {
    // 首先写递归的终止条件
    if (n == 1) return 1;
    // n 加 1 ~ n-1 的和
    int tmp = sum(n-1);
    int res = n + tmp;
    return res;
}

二、斐波那契数列

问题：求第n个斐波那契数。

public int fibonacci(int n) {
    // 首先写递归的终止条件
    if (n == 1) return1;
    if (n == 2) return2;
    // 求解子问题
    // 求解n-1的子问题
    int fib1 = fibonacci(n - 1);
    int fib2 = fibonacci(n - 2);
    return fib1 + fib2;
}

三、走台阶

前面两个例子都比较好理解。
在本例中，f(n)表示走n个台阶的走法。一次最多走两级台阶。
先走了1个台阶，剩下 n-1 个台阶的走法是：f(n-1)
先走了2个台阶，剩下 n-2 个台阶的走法是：f(n-1)
那么 f(n) = f(n-1) + f(n-2)
f(n-1) = f(n-2) + f(n-3)
...
f(1) = 1 若此时只有1个台阶，只有一种走法。
f(2) = 2 若此时有2个台阶，可以一阶一阶走，也可以一次走两阶，一共两种走法。

这样，我们同样的把一个大问题，拆成两个子问题。

// 1. 写出递推公式  f(n) = f(n-1) + f(n-2)
// 2. 写递归的终止条件  f(1) = 1; f(2) = 2 ;
public int walkStair(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int res = walkStair(n - 1) + walkStair(n - 2);
    return res;
}