递归 属于

关于 递归

递归是一种通过在函数内部调用函数自身来反复执行代码的方式。 调用自身的函数称为_递归_函数。 递归可以看作循环/迭代的另一种方式。 和循环一样，递归也用布尔表达式或 True/False 判断来决定何时停止递归执行。

与_循环_不同，Python 中没有终止条件的递归无法无限地运行下去。 每次函数调用所使用的值都会放在 Python 解释器栈上各自的帧里。 如果函数调用的总数占用的空间超过了栈所能容纳的容量，就会导致错误。

循环与递归实现

循环和递归在都是迭代这一点上可能_感觉_相似。 然而，无论是在代码层面还是实现层面，它们_看起来_都不一样。 循环可以在调用栈上的同一帧内进行。 这通常是通过更新一个或多个变量的值、逐步为每次迭代维持状态来完成的。 这是一种高效的实现，但看代码时可能会显得有些杂乱。

递归不更新_变量状态_，而是把_更新后的值_直接作为实参传给同一个函数的下一次调用（迭代）。 这能让函数体更简洁，也能让每次更新如何发生变得更清楚。 不过，它的效率也更低，因为对同一个函数的每次调用都会在栈上再增加一帧。

递归：用还是不用？

既然有引发栈错误或栈溢出的风险，为什么还会有人用递归策略来解决问题呢？ 可读性、可追踪性和意图。 有些情况下，用递归表达的解法可能比用循环表达的解法更易读，也更容易推理。 也可能存在一些程序上的约束，比如数据的使用与修改、复杂度的管理、职责的委派，或工作负载的组织。

适合用递归解决的问题包括那些复杂但重复、并且规模会逐渐变小的问题，尤其是分治算法和累加算法。 然而，由于 Python 对栈上允许的帧数有限制，并不是所有问题都能从完全递归的策略中获益。 不太适合递归的问题包括：处于稳定状态、但需要重复固定次数的问题，需要异步执行的问题，以及需要大量迭代的场景。

循环与递归策略：Indira 的不安

Indira 每个月的社保金都会在每个月的**第二个星期三**自动存入她的银行账户。 Indira 担心自己对不上账。 她担心自己会在钱存入之前就把支票开出去。 她请孙女 Adya 帮她列出一份钱会到账的日期清单。

Adya 刚开始学用 Python 编程，她根据自己的第一想法写了一个程序。 她想返回一个包含各次到账日期的 list，以便把它们打印出来。 她希望写出的函数对_任何年份_都适用。 万一时间表有变（或者万一其他亲戚也想让 Adya 计算他们的到账日期），她决定让函数额外接收一个表示_星期几_的形参。 最后，Adya 决定函数还需要一个形参来表示它是这个月的_第几个_该星期几：第一个、第二个，等等。 综合这些需求，她决定使用从 datetime 导入的 date 类。 把这些放在一起，Adya 写出了：

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

这第一版能正常工作，但 Adya 想知道能不能重构代码，用更少的行数和更少的嵌套循环。 她还读到过，尽量减少状态的修改是件好事，所以她想看看能不能避免修改 output、month 和 day_num 这类变量。

她也了解递归，于是思考如何把自己的程序改成递归的思路。 她循环版函数中创建并修改的那些变量，其实可以改为以实参的形式传进去。 与其在函数_内部_修改变量，她可以把_更新后的值作为实参_传给下一次函数调用。 带着这些想法，她写出了这样的递归方案：

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Adya 很高兴：没有嵌套循环了，没有被修改的状态了，代码还少了 2 行！

她有点担心递归方案比循环方案用了更多步骤，因此“性能”没那么好。 但用递归重写这个问题，确实帮她解决了难看的嵌套循环（性能隐患）、大量的状态修改，以及复杂条件逻辑带来的困惑。 它读起来也更“可读”了，她确信，等自己休息一段时间再回来看这段代码时，能更轻松地读懂并记起它的作用。

将来，Adya 可能会先尝试用递归来解决问题。 她可能会发现，当嵌套、修改和复杂度都被降到最低时，一开始用清晰的步骤梳理问题会更容易。 理清基本逻辑之后，她就可以专注于把最初的递归步骤优化成性能更好的循环方案。

再往后，当她学到 tuples 时，Adya 还可以考虑进一步的“优化”方法，比如把 list comprehension 和 Calendar.itermonthdates 一起使用，或者对某些值做记忆化。

递归的变体：尾调用

尾调用是指函数的最后一条语句只是调用它自己，除此之外不做别的。 下面这个例子不是尾调用，因为函数给自己的调用结果又加了 1：

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

它会打印出：

The step is 1
The step is 2
retval is 3 after recursion

要把它重构成尾调用，把 retval 变成 print_increment 的形参。

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

你可能会发现，尾调用甚至比不是尾调用的递归调用更容易推理。 不过，使用递归时始终要清楚：迭代次数不能多到让栈溢出。

Python 中的递归限制

有些语言能够优化尾调用，让每次递归调用都复用函数第一次调用时的栈帧（类似循环复用帧的方式），而不是在栈上再加一帧。 Python 不属于这类语言。 为了防止栈溢出，Python 设有递归限制，默认为 1000 帧。 当解释器检测到超过递归限制时，会抛出 RecursionError 异常。 可以用 sys.setrecursionlimit 方法来提高递归限制，但这样做有产生运行时段错误的风险，会导致程序崩溃，甚至可能让操作系统也崩溃。

资源

想进一步了解如何在 Python 中使用递归，可以从下面这些开始：

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively