青蛙跳台阶-递归思想解算

问题：一只青蛙一次可以跳上一级台阶，也可以跳上两级台阶。求该青蛙跳上n级台阶总共有多少种跳法？

思路：要跳上第n级台阶，要么从第 n-1 级台阶跳上，要么从第 n-2 级台阶跳上，只有这两种方法。因此，跳上第n级台阶的跳法等于跳上第n-1级的跳法加上跳上第n-2级的跳法。采用递归算法实现。

基线条件：if n == 0 or n == 1 or n == 2: return n

递归公式：f(n) = f(n-1) + f(n-2)

代码：

def stairs(n):

    # 基线条件 => 跳出递归调用
    if n == 0 or n == 1 or n == 2:
        return n
    
    # 递归公式：实现递归调用
    return stairs(n-1) + stairs(n - 2)


print(stairs(5))

>>>
8

2020年11月30日修改：
使用递归求解，当台阶数n过大时(>50)，就会比较耗时了；
因此需要更改方式，观察规律可知：f(n) = f(n-1) + f(n-2)，属于斐波那契数列。
故代码如下：

def stairs(n):
    n1 = 1  # 一级台阶跳法数
    n2 = 2  # 二级台阶跳法数
    
    # 一级、二级台阶直接返回，三级台阶以上循环计算n级台阶前两级跳法和
    # 例如：n = 3，n3 = n1 + n2，由于只使用两个位置存储数值，则需要更新n1, n2
    # n2 = n1 + n2, n1 = n2。以继续计算n>3的情况。（最后n2即为结果）
    if n == 1:
        return n1
    elif n == 2:
        return n2
    else:
        for i in range(3, n + 1):
            n1, n2 = n2, n1 + n2
        return n2

补充：

1）递归函数优点 => 定义简单，逻辑清晰；

缺点：使用递归函数需要注意防止栈溢出。

递归调用时使用栈来保护现场和恢复现场，也很耗费资源。

2）计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。(RuntimeError: maximum recursion depth exceeded in comparison = > 运行错误：超出最大递归深度。)

python默认栈的层数为1000层

3）使用尾递归进行优化：在递归函数返回的递归公式中直接调用自身本身，而不是返回计算表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

需要每次调用时都直接计算结果，并将每次调用的前结果暂存起来。

4）遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把递归函数改成尾递归方式，也会导致栈溢出。

尾递归：

# 尾递归计算num的阶乘
def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

return fact_iter(num - 1, num * product)仅返回递归函数本身，num - 1和num * product在函数调用前就会被计算，不影响函数调用。

最后编辑于：2020.11.30 22:10:26