一、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;
}
