根据以上递归公式我们补充一下函数的功能
public int allCells(int n) { return aCell(n) + bCell(n) + cCell(n); } /** * 第 n 小时 a 状态的细胞数 */ public int aCell(int n) { if(n==1){ return 1; }else{ return aCell(n-1)+bCell(n-1)+cCell(n-1); } } /** * 第 n 小时 b 状态的细胞数 */ public int bCell(int n) { if(n==1){ return 0; }else{ return aCell(n-1); } } /** * 第 n 小时 c 状态的细胞数 */ public int cCell(int n) { if(n==1 || n==2){ return 0; }else{ return bCell(n-1); } }只要思路对了,
,另一方面也告诉我们，可能一时的递归关系我们看不出来,此时可以借助于画图来观察规律
求时间复杂度 由第二步的递推公式我们知道 f(n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)
之前青蛙跳台阶时间复杂度是指数级别的，而这个方程式显然比之前的递推公式(f(n) = f(n-1) + f(n-2)) 更复杂的，所以显然也是指数级别的
结语大部分递归题其实还是有迹可寻的,按照之前总结的解递归的四个步骤可以比较顺利的解开递归题,一些比较复杂的递归题我们需要勤动手,画画图,观察规律,这样能帮助我们快速发现规律,得出递归公式,一旦知道了递归公式,将其转成递归代码就容易多了,很多大厂的递归考题并不能简单地看出递归规律,往往会在递归的基础上多加一些变形,不过万遍不离其宗，我们多采用自顶向下的分析思维,多练习，相信递归不是什么难事。
[x] 好文同步更新到我的站点智客坊
参考一文教你学会递归解题
