有趣的递归思想

什么是递归

去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。

递归需要满足的三个条件

1、一个问题的解可以分解为几个子问题的解

子问题就是数据规模更小的问题。

2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

3、存在递归终止条件

跳出无限循环的条件

如何编写递归代码？

关键的是写出递推公式，找到终止条件

总体思路：找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

警惕点

递归代码要警惕堆栈溢出

每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)

台阶问题

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？

递归解法

class FootstepCountNew:
    """
    优化重复计算
    """
    def __init__(self):
        self.mykeys = {}

    def run(self, n):
        if n == 1:
            return 1

        if n == 2:
            return 2

        if n in self.mykeys:
            return self.mykeys[n]

        result = self.run(n-1) + self.run(n-2)
        self.mykeys[n] = result
        return result

非递归解法

def f1(n):
    a = 0
    b = 1
    output = []

    for i in range(n):
        b, a = a+b, b
        output.append(b)

    print(output)
    print(b)

思考

我们平时调试代码喜欢使用 IDE 的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？

• 打印日志发现，递归值。
• 结合条件断点进行调试。