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))

递归的优点:

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

递归的缺点:

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