给定一道题假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶总共有多少种不同的方法当 n 很大时我们很难一眼猜出数量。我们不妨把 n 设定成很小的值来看。n1 时只有爬一步这一种方法方法数为 1n2 时可以爬两次一步也可以一次爬两步方法数为 2n3 时可以爬三次一步也可以爬一次一步再爬一次两步反过来爬一次两步再爬一次一步方法数为 3此时我们发现312这是否表明台阶为 n 时其方法数与台阶为 n-1、n-2 的方法数有相加关系呢多探索一层n4时爬4次一步爬2次两步爬2次一步 1次2步爬1次两步 2次一步爬1次一步1次两步再爬1次一步方法数为5532符合我们的假设式F(n)F(n-1)F(n-2); 注F(n)表示台阶为n时的方法数为了更直观地理解这个递推关系我们以 F(5) 为例画出它的递归调用树。每个节点代表一次方法调用节点下方的数字表示该子问题的结果flowchart TD F5[F(5) 5] F4[F(4) 3] F3a[F(3) 2] F3b[F(3) 2] F2a[F(2) 2] F1a[F(1) 1] F2b[F(2) 2] F1b[F(1) 1] F2c[F(2) 2] F1c[F(1) 1] F5 -- F4 F5 -- F3a F4 -- F3b F4 -- F2a F3a -- F2b F3a -- F1a F3b -- F2c F3b -- F1b F2a -- F1c从图中可以看到F(5) 会先拆分成 F(4) 和 F(3)而 F(4) 又继续拆分成 F(3) 和 F(2)F(3) 再拆分成 F(2) 和 F(1)。当拆分到 F(1) 和 F(2) 这两个已知结果时递归停止然后逐层向上返回最终得到 F(5) F(4) F(3) 3 2 5。为什么会有这个等式呢我们来做一次抽象假设n很大大到了100。要想得知此时的方法数我们设想要想踏上第100阶那么上一步应该在哪显然第97阶不能不能一步跳三阶到达100只剩下98 和 99 两阶一个可以爬1次两步到达一个可以爬1次一步到达。那么推理可得n100的总方法数应该是n98和n99的方法数相加因为这两阶都只有一个方法到达100此时我们宣布算出来了就是这两个相加至于这两个数是多少我们算n100的人并不关心应该交由算n99和n98的人来得出。他们在计算时也能轻易得出F(99)F(98)F(97);F(98)F(97)F(96)。而依旧把更小的n交由他人计算以此类推直到n1和n2我们惊喜的发现这两个我们一开始就知道了分别等于1 和 2。将其步步往上提交返回我们最终能算出来最终的结果。这就是递归的核心思想将一个大的问题拆分成无数小的问题往下调取直至获取到最小的不可计算想返回。现在我们编写一个可以执行的方法public long F(int n){ if(n1){ return 1; } else if(n 2){ return 2; } else{ return F(n-1)F(n-2); } }该方法接收int n;假如n1或2时能直接返回。当没有可直接返回时会返回F(n-1)F(n-2);执行时会继续调用F方法进行计算直至返回1或2。该方法能做到较小n时的快速返回但由于没有进行优化不建议输入较大值。n每增加1所要执行的子方法几乎要翻一倍。
