经典的斐波那契系题目(走台阶、青蛙跳、汉诺塔、兔子繁衍等) 1 1 2 3 5 8 13 21 34 55 89
递归解题思路：递推+回归

第一步，递推：目标是想求n级台阶有多少种走法，现在先假设已经走完了n级台阶同时假设存在f(n)种走法可以走完n级台阶，现在退回到走完这n级台阶的上一步，即走完这n级台阶的最后一步，最后一步有两种可能的情况，第一种情况是这一步只走了1级台阶，即完成最后一步之前已经走了n-1级台阶，假设走完n-1级台阶存在f(n-1)种走法；第二种情况是最后一步走了两级台阶，即完成最后一步之前已经走了n-2级台阶，又假设走完n-2级台阶存在f(n-2)种走法，那么理一下思路：完成n级台阶最后一步之前需要走完n-1级台阶或者n-2级台阶，因为n级存在台阶f(n)种走法，n-1级台阶存在f(n-1)种走法，n-2级台阶存在f(n-2)种走法，所以f(n)=f(n-1)+f(n-2);
继续递推，完成n-1级台阶的最后一步时之前肯定走了n-2或n-3级台阶，再继续递推，走完n-2级台阶的最后一步时之前肯定走了n-3或n-4级台阶，一直递推下去，则有：f(n) = f(n-1)+f(n-2) , f(n-1) = f(n-2)+f(n-3) , f(n-2) = f(n-3)+f(n-4) , f(n-3) = f(n-4)+f(n-5) , ...... , f(4) = f(3)+f(2) , f(3) = f(2)+f(1) 至此，递推结束。

第二步，回归：分析上面递推中的表达式可知，f(n)的结果依赖于f(n-1)和f(n-2)，f(n-1)的结果依赖于f(n-2)和f(n-3)，每一项都是未知数，无法求解，只能一直依赖下去，直到最后依赖到f(1)和f(2)的头上，也就是说只要f(1)和f(2)不是未知数，就可以逆着递推的顺序回归到f(n)，解出f(n)。求f(1)和f(2)：根据递推中的假设规律f(1)是指走1级台阶的走法，因为一级台阶只有一种走法，因此f(1)=1；f(2)是走2级台阶的走法，二级台阶的走法可以是先走一级再走一级或者直接走两级，因此f(2)=2。

问题就这样解决了，递归代码很好写，但是需要注意当n较大时，由于递归层数多，空间和时间消耗比较大，甚至会出现超时超内存的情况，比在python中默认递归调用深度为1000，当n大于1000时会抛出超过最大调用深度的错误RecursionError: maximum recursion depth exceeded while calling a Python object.因此，往往可以把递归的写法改用循环来实现。