python递归与迭代:N级楼梯，每次只能跨1或2级，共有几种走法?

思考：N级楼梯,每次只能跨1或2级,走完这楼梯共有多少种走法？

解题思路：数学递推法

N级楼梯,每次只能跨1或2级,走法记为F(N)，下面用两种方法来求解F(N)

1、当N=1时，只有1级楼梯，故只能跨1级，只有1种走法，即F(1)=[(1)]=1

2、当N=2时，可以每次都只跨1级走完楼梯，或直接跨2级走完楼梯，故有2种走法，即F(2)=[(1,1),(2)]=2

3、当N>=3时，最后一步走法有两种情况：

情况1：若最后一步是跨1级，则是从N-1级楼梯直接跨1级走完楼梯的，故走完N-1级楼梯有多少种走法，这种情况就有多少种走法，有F(N-1)种走法。

情况2：若最后一步是跨2级，则是从N-2级楼梯直接跨2级走完楼梯的，故走完N-2级楼梯有多少种走法，这种情况就有多少种走法，有F(N-2)种走法。

所以，当N>=3时，共有走法：F(N)=F(N-1)+F(N-2)

递推过程

F(1)=1

F(2)=2

F(3)=F(2)+F(1)=2+1=3

F(4)=F(3)+F(2)=3+2=5

依此类推

F(N)=F(N-1)+F(N-2)

python代码实现：

（1）递归算法

import time

print('n级楼梯,每次跨1级或2级,有多少种走法')

'''
1、递归算法
'''


def fun_recursive_algorithm(n):
    fn = 0
    try:
        if n < 0:
            return fn
        elif n == 1:
            fn = 1
        elif n == 2:
            fn = 2
        elif n >= 3:
            fn = fun_recursive_algorithm(n-1) + fun_recursive_algorithm(n-2)
    except Exception as err:
        print('递归算法计算异常：' + str(err))
    finally:
        return fn

print('1、递归算法')
for i in range(1, 50):
    start_time = time.time()  # 开始运行时间
    fn = fun_recursive_algorithm(i)
    end_time = time.time()  # 运行结束时间
    run_time = float(end_time-start_time)*1000  # 计算运行时间，即计算过程耗时（毫秒）
    print(f'{i}级楼梯,每次跨1级或2级,有{fn}种走法,递归算法耗时：{run_time} 毫秒')

递归算法运行结果如下：

（2）迭代算法

import time

print('n级楼梯,每次跨1级或2级,有多少种走法')
'''
2、迭代算法
'''


def fun_iterative_algorithm(n):
    fn = 0  # n级楼梯走法
    fn_1 = 0  # n-1级楼梯走法
    fn_2 = 0  # n-2级楼梯走法

    try:
        for i in range(1, n+1):
            if i == 1:
                fn = 1  # n=1 级楼梯走法
            elif i == 2:
                fn = 2  # n=2 级楼梯走法
                fn_1 = 1  # n-1=1 级楼梯走法
            elif i >= 3:
                fn_2 = fn_1  # 因为i+=1，所以本次的n-2 为上次的n-1 级楼梯走法
                fn_1 = fn  # 因为i+=1，所以本次的n-1 为上次的n 级楼梯走法
                fn = fn_1 + fn_2
    except Exception as err:
        print('迭代算法计算异常：' + str(err))
    finally:
        return fn


print('2、迭代算法')
for i in range(1, 30):
    start_time = time.time()  # 开始运行时间
    fn = fun_iterative_algorithm(i)
    end_time = time.time()  # 运行结束时间
    run_time = float(end_time-start_time)*1000  # 计算运行时间，即计算过程耗时（毫秒）
    print(f'{i}级楼梯,每次跨1级或2级,有{fn}种走法,递归算法耗时：{run_time} 毫秒')

迭代算法运行结果如下：

大家可以通过这个案例来感受一下递归算法与迭代算法的区别。

思考题：

本题除了用上述数学中递推法来解题，你们还有什么方法可以解题吗？

个人感觉：其实这个问题用数学的组合方法也可以解题的，下一章，我将与各位一起探讨和使用数学中的组合方法来解题！！！