一文学会递归解题
递归的实战演练（入门级）
热身赛
输入一个正整数n，输出n!的值。其中n!=123…n,即求阶乘
套用上一节我们说的递归四步解题套路来看看怎么解：
1.定义这个函数，明确这个函数的功能，我们知道这个函数的功能是求 n 的阶乘, 之后求 n-1, n-2 的阶乘就可以调用此函数了
/**
* 求 n 的阶乘
*/
public int factorial(int n) {
}2.寻找问题与子问题的关系 阶乘的关系比较简单， 我们以 f(n) 来表示 n 的阶乘， 显然 f(n) = n * f(n - 1), 同时临界条件是 f(1) = 1,即
3. 将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中
/**
* 求 n 的阶乘
*/
public int factorial(int n) {
// 第二步的临界条件
if (n < =1) {
return1;
}
// 第二步的递推公式
return n * factorial(n-1)
}4.求时间复杂度 由于 f(n) = n f(n-1) = n (n-1) .... f(1),总共作了 n 次乘法，所以时间复杂度为 n。
看起来是不是有这么点眉目， 当然这道题确实太过简单,很容易套路，那我们再来看进阶一点的题。
入门题
一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:
跳上第 1 级台阶只有一种跳法：直接跳 1 级即可。跳上第 2 级台阶
有两种跳法：每次跳 1 级，跳两次；或者一次跳 2 级。
问要跳上第 n 级台阶有多少种跳法？
我们继续来按四步曲来看怎么套路。
1.定义一个函数，这个函数代表了跳上 n 级台阶的跳法
/**
* 跳 n 极台阶的跳法
*/
public int f(int n) {
}2.寻找问题与子问题之前的关系 这两者之前的关系初看确实看不出什么头绪，但仔细看题目，一只青蛙只能跳一步或两步台阶，自上而下地思考，也就是说如果要跳到 n 级台阶只能从 从 n-1 或 n-2 级跳， 所以问题就转化为跳上 n-1 和 n-2 级台阶的跳法了，如果 f(n) 代表跳到 n 级台阶的跳法，那么从以上分析可得 f(n) = f(n-1) + f(n-2),显然这就是我们要找的问题与子问题的关系,而显然当 n = 1, n = 2， 即跳一二级台阶是问题的最终解，于是递推公式系为
3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中 补充后的函数如下
/**
* 跳 n 极台阶的跳法
*/
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
return f(n-1) + f(n-2)
}4.计算时间复杂度 由以上的分析可知 f(n) 满足以下公式
斐波那契的时间复杂度计算涉及到高等代数的知识， 这里不做详细推导，有兴趣的同学可以点击这里查看,我们直接结出结论。
由些可知时间复杂度是指数级别，显然不可接受，那回过头来看为啥时间复杂度这么高呢,假设我们要计算 f(6),根据以上推导的递归公式，展示如下
可以看到有大量的重复计算, f(3) 计算了 3 次， 随着 n 的增大，f(n) 的时间复杂度自然呈指数上升了
5.优化
既然有这么多的重复计算，我们可以想到把这些中间计算过的结果保存起来，如果之后的计算中碰到同样需要计算的中间态，直接在这个保存的结果里查询即可，这就是典型的 以空间换时间,改造后的代码如下
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
// map 即保存中间态的键值对， key 为 n，value 即 f(n)
if (map.get(n)) {
return map.get(n)
}
return f(n-1) + f(n-2)
}那么改造后的时间复杂度是多少呢，由于对每一个计算过的 f(n) 我们都保存了中间态 ，不存在重复计算的问题，所以时间复杂度是 O(n), 但由于我们用了一个键值对来保存中间的计算结果，所以空间复杂度是 O(n)。问题到这里其实已经算解决了，但身为有追求的程序员，我们还是要问一句,空间复杂度能否继续优化?
6.使用循环迭代来改造算法 我们在分析问题与子问题关系（f(n) = f(n-1) + f(n-2)）的时候用的是自顶向下的分析方式,但其实我们在解 f(n) 的时候可以用自下而上的方式来解决，通过观察我们可以发现以下规律
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 5
....
f(n) = f(n-1) + f(n-2)最底层 f(1), f(2) 的值是确定的，之后的 f(3), f(4) ,...等问题都可以根据前两项求解出来，一直到 f(n)。所以我们的代码可以改造成以下方式
public int f(int n) {
if (n == 1) return1;
if (n == 2) return2;
int result = 0;
int pre = 1;
int next = 2;
for (int i = 3; i < n + 1; i ++) {
result = pre + next;
pre = next;
next = result;
}
return result;
}改造后的时间复杂度是 O(n), 而由于我们在计算过程中只定义了两个变量（pre，next），所以空间复杂度是O(1)
简单总结一下：分析问题我们需要采用自上而下的思维，而解决问题有时候采用自下而上的方式能让算法性能得到极大提升,思路比结论重要。
递归的实战演练(进阶级)
来源 | 五分钟学算法
作者 | 码海
