Python 递归函数

本教程作者所著新书《Python之光：Python编程入门与实战》（ISBN：9787111729891）已由机械工业出版社出版上市，各大电商平台有售，欢迎：查看详情并关注购买。

编程中，在函数内部，调用函数自身的编程技巧称为递归（ 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

报错

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

RecursionError: maximum recursion depth exceeded in comparison

参考

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

相关内容

• Python习题 120：判断数字是几位数 2023-09-21 20:58:41