递归思维：计算爬楼梯歩法

问题描述：

爬楼梯，可以一步一梯，也可以一步两梯，问：走N级台阶有多少种步法？

问题算法：

设走上n级台阶有f(n)种方法，将这n种方法拆分为两大类：

1、最后一次走了一级台阶，那么此前有f(n-1)种步法；

2、最后一次走了二级台阶，那么此前有f(n-2)种步法；

3、得出递推公式：f(n)=f(n-1)+f(n-2)；

4、显而易见，f(1)=1，f(2)=2。

Python代码如下：

def climbStairs(n):

if n==1:

return 1

elif n==2:

return 2

else:

return(climbStairs(n-1)+climbStairs(n-2))

n=int(input("请输入要走的台阶数n："))

print(climbStairs(n))

学习心得：

关键点在于从最后一步往前推，让人顿时豁然开朗。虽然递归算法的代码效率不高，但好处在于思路非常的简单清晰。感觉递归的思考方式非常给力，平时生活学习中是否有类似应用场景呢？