1.第一种，归纳法，一个台阶的时候只有1中方法，2个台阶的时候2种方法，3个台阶的时候可以分为2部分，将前面两个台阶认为是1个，相当于2个台阶，还是2种方法，再乘以前面一部分的方法数量就是3个台阶的方法数量，以此类推，每增加一个台阶，走的方法是少一个台阶时候的2倍，因此这个算法可以这样写：
func = lambda x: 1 if x<2 else 2*func(n-1)
2.
def test(n): a=0 if n==0: a=1 for i in range(1,n+1): a+=test(n-i) return a
原文：http://www.cnblogs.com/lowseasonwind/p/7215389.html