干货满满！全面详解如何用递归解题( 四 ) _递归

有人问第一步的 n - 1 怎么从 C 移到 B,重复上面的过程,只要把上面的 n-2个盘子经由 A 移到 B, 再把A最下面的盘子移到 C,最后再把上面的 n - 2 的盘子经由A 移到 B 下..., 怎么样，是不是找到规律了，不过在找问题的过程中切忌把子问题层层展开,到汉诺塔这个问题上切忌再分析 n-3,n-4 怎么移，这样会把你绕晕，只要找到一层问题与子问题的关系得出可以用递归表示即可。
由以上分析可得
move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)
一定要先得出递归公式，哪怕是伪代码也好!这样第三步推导函数编写就容易很多，终止条件我们很容易看出，当 A 上面的圆盘没有了就不移了
3.根据以上的递归伪代码补充函数的功能
// 将 n 个圆盘从 a 经由 b 移动到 c 上public voidhanoid(int n, char a, char b, char c) {if (n <= 0) {return;}// 将上面的 n-1 个圆盘经由 C 移到 Bhanoid(n-1, a, c, b);// 此时将 A 底下的那块最大的圆盘移到 Cmove(a, c);// 再将 B 上的 n-1 个圆盘经由A移到 C上hanoid(n-1, b, a, c);}public voidmove(char a, char b) {printf("%c->%cn", a, b);}从函数的功能上看其实比较容易理解，整个函数定义的功能就是把 A 上的 n 个圆盘经由 B 移到 C，由于定义好了这个函数的功能，那么接下来的把 n-1 个圆盘经由 C 移到 B 就可以很自然的调用这个函数,所以明确函数的功能非常重要,按着函数的功能来解释，递归问题其实很好解析，切忌在每一个子问题上层层展开死抠,这样这就陷入了递归的陷阱，计算机都会栈溢出，何况人脑
4.时间复杂度分析从第三步补充好的函数中我们可以推断出
f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1= 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 22 * f(n-3) + 2 + 1= 22 * f(n-3) + 2 + 1 = 22 * (2f(n-4) + 1) = 23 * f(n-4) + 22 + 1= .... // 不断地展开= 2n-1 + 2n-2 + ....+ 1
显然时间复杂度为 O(2n)，很明显指数级别的时间复杂度是不能接受的，汉诺塔非递归的解法比较复杂，大家可以去网上搜一下

进阶题现实中大厂中的很多递归题都不会用上面这些相对比较容易理解的题，更加地是对递归问题进行相应地变形，来看下面这道题

细胞分裂有一个细胞每一个小时分裂一次，一次分裂一个子细胞，第三个小时后会死亡。那么n个小时候有多少细胞？

照样我们用前面的递归四步曲来解
1.定义问题的递归函数，明确函数的功能我们定义以下函数为 n 个小时后的细胞数
public int allCells(int n) {}2.接下来寻找问题与子问题间的关系（即递推公式）首先我们看一下一个细胞出生到死亡后经历的所有细胞分裂过程

文章插图
图中的 A 代表细胞的初始态, B代表幼年态(细胞分裂一次), C 代表成熟态(细胞分裂两次)，C 再经历一小时后细胞死亡以 f(n) 代表第 n 小时的细胞分解数fa(n) 代表第 n 小时处于初始态的细胞数,fb(n) 代表第 n 小时处于幼年态的细胞数fc(n) 代表第 n 小时处于成熟态的细胞数则显然 f(n) = fa(n) + fb(n) + fc(n)那么 fa(n) 等于多少呢，以n = 4 （即一个细胞经历完整的生命周期）为例
仔细看上面的图
可以看出fa(n) = fa(n-1) + fb(n-1) + fc(n-1), 当 n = 1 时，显然 fa(1) = 1
fb(n) 呢,看下图可知 fb(n) = fa(n-1) 。当 n = 1 时 fb(n) = 0

文章插图
fc(n) 呢,看下图可知 fc(n) = fb(n-1) 。当 n = 1,2 时 fc(n) = 0

文章插图
【干货满满！全面详解如何用递归解题】综上，我们得出的递归公式如下
f(n) = fa(n) + fb(n) + fc(n)
3.根据以上递归公式我们补充一下函数的功能

public int allCells(int n) {return aCell(n) + bCell(n) + cCell(n);}/*** 第 n 小时 a 状态的细胞数*/public intaCell(int n) {if(n==1){return 1;}else{return aCell(n-1)+bCell(n-1)+cCell(n-1);}}/*** 第 n 小时 b 状态的细胞数*/public intbCell(int n) {if(n==1){return 0;}else{return aCell(n-1);}}/*** 第 n 小时 c 状态的细胞数*/public intcCell(int n) {if(n==1 || n==2){return 0;}else{return bCell(n-1);}}

只要思路对了，将递推公式转成代码就简单多了，另一方面也告诉我们，可能一时的递归关系我们看不出来，此时可以借助于画图来观察规律
4.求时间复杂度由第二步的递推公式我们知道f(n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)
之前青蛙跳台阶时间复杂度是指数级别的，而这个方程式显然比之前的递推公式(f(n) = f(n-1) + f(n-2)) 更复杂的，所以显然也是指数级别的