Python 递归函数

Jinku Hu 2023年1月30日
  1. 什么是 Python 递归函数
  2. 递归次数限制
  3. 递归的优点
  4. 递归的缺点
Python 递归函数

我们这节来学习 Python 递归函数。

什么是 Python 递归函数

递归函数是一个调用自身的函数,这个过程称为函数递归。比如,让我们计算数字 6 的阶乘。

6 * 5 * 4 * 3 * 2 * 1

在以下代码中,我们创建了一个递归函数,用来计算某个数字的阶乘。

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))
Factorial of 6 = 720

函数 fact(n) 是一个递归函数,它用参数 n-1 调用自身,直到参数变为 1 为止,这就是计算阶乘的方法,即将数字乘以比这数字小 1 的数的阶乘,fact(n)=n*fact(n-1),就得到了这个数字的阶乘。

在这个递归函数中,有一个结束条件,当数字变为 1 时,返回 1,不再继续调用函数自身,这样递归调用就是有限次数的调用。

在创建递归函数时,必须有一个这样的结束条件来终止递归调用。

递归次数限制

也许你已经注意到了,每次函数调用自身时,都需要一些内存来存储一些中间值。因此,递归函数比正常的非递归函数消耗更多的内存。Python 将递归调用次数限制设置为 3000

>>> import sys
>>> sys.getrecursionlimit()
3000

如果递归次数超过 3000 次的话,它会触发 RecursionError

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(3000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

移除递归限制的方法

你可以通过将递归限制次数设置为大于所需递归次数的数字来解除递归次数的限制。

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

递归的优点

  • 使用递归函数,可以将问题分解为子问题来轻松解决。
  • 代码变得整洁干净。

递归的缺点

  • 有时很难去设计和理解递归函数的逻辑。
  • 解决每个子问题将花费大量时间,因此递归函数效率低下。
作者: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

DelftStack.com 创始人。Jinku 在机器人和汽车行业工作了8多年。他在自动测试、远程测试及从耐久性测试中创建报告时磨练了自己的编程技能。他拥有电气/电子工程背景,但他也扩展了自己的兴趣到嵌入式电子、嵌入式编程以及前端和后端编程。

LinkedIn Facebook