Python 递归函数

说明

《Python 教程》持续更新中，提供建议、纠错、催更等加作者微信: gairuo123（备注：pandas教程）和关注公众号「盖若」ID: gairuo。跟作者学习，请进入 Python学习课程。欢迎关注作者出版的书籍：《深入浅出Pandas》和《Python之光》。

编程中，在函数内部，调用函数自身的编程技巧称为递归（ recursion）。递归函数结构清晰，很直观的理解计算过程，但也有严重缺点：相对于普通循环而言，递归运行效率较低，经过很多冗余的计算，递归会消耗大量的调用堆栈。

理解

我们在讲迭代的时候提到过递归，迭代和递归都是将一件事情不断重复做下去，直到做完，不过思路不一样。简单来说，一个函数中有调用自身的情况就是递归，比如 Python 内置模块的 functools.reduce 就是一个典型的递归函数，它在处理可迭代内容时，每次传入两个参数，第一个永远是 reduce 计算过的值。

迭代和递归都是一个事情多次重复下去，解决问题，不过思路不一样。

例子：

递归：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！...
迭代：愚公移山，子子孙孙无穷无尽，干同一件事情。

示例

以下是一个斐波那契数列的例子，可以实现第几位是什么值。

def fibo(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2) 

fibo(4)  # 3

阶乘是递归函数的经典示例：

# 计算阶乘
def factorial(n: int) -> int:
    if n == 0:
        return 1  # 基本情况
    else:
        return n * factorial(n - 1)  # 递归情况

# 示例使用
factorial(5) # 120

报错

递归不能无限进行下去，受限于系统资源，如果超出会报 RecursionError 类型错误，具体为：

RecursionError: maximum recursion depth exceeded in comparison

参考

https://www.programiz.com/python-programming/recursion

Python 递归函数

理解

示例

报错

参考

相关内容