Select Language

AI社区

AI技术百科

3.6、Python递归函数实例详解

递归调用是高级编程语言的基本特性,它最早出现在 LISP 语言中。Python 语言也支持递归调用。通过递归调用可以简化代码,而且可以让代码和问题的数学描述非常一致。使用递归调用一般不会提升代码运行速度。

什么是递归调用

递归调用是一种特殊的嵌套调用,是指某个函数调用自己或者调用其他函数后再次调用自己。由于不能无限嵌套调用,所以某个递归函数一定存在至少两个分支,一个是退出嵌套,不再直接或者间接调用自己;另外一个则是继续嵌套。

一般通过函数的输入参数来决定走哪个分支,所以递归函数一般都是带有参数的。

递归调用的实例

1、求阶乘

最常见的递归用法是求一个整数的阶乘,如 2 的阶乘等于 1×2,3 的阶乘等于 1×2×3。如果不用递归的方法,可以使用下面的方法来实现。

>>> def get_factorial(n):                      # 定义阶乘函数
...     ret = i = 1
..     while i <= n:                           # 从1到n,依次相乘
...             ret = ret * I
...             i = i + 1
...     return ret                             # 返回值
...                                            # 阶乘函数定义结束
>>> get_factorial(3)                           # 求3的阶乘
6
>>> get_factorial(10)                          # 求10的阶乘
3628800

如果使用递归方法,可以定义下面的求值方案:


如果 n>1,就可以递归调用阶乘函数自己了,代码如下:

>>> def get_factorial(n):                              # 定义阶乘函数
...     if n == 1:                                     # 退出递归的分支
...         return 1
...     return n * get_factorial(n-1)   # 递归调用
...                                                    # 阶乘函数定义结束
>>> get_factorial(3)                                   # 求3的阶乘
6
>>> get_factorial(10)                                  # 求10的阶乘
3628800


递归需要注意递归的深度。由于递归会产生多次函数调用,而函数调用会消耗代码的栈空间,如果递归的深度太大,会导致栈溢出。以上面的阶乘为例,如果计算 100000 的阶乘,在一般机器上都会出现栈溢出的问题,如下所示:

>>> get_factorial(100000)             # 求100000的阶乘
Traceback (most recent call last):    # 错误信息
File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in get_factorial
  File "<stdin>", line 4, in get_factorial
  File "<stdin>", line 4, in get_factorial
  [Previous line repeated 994 more times]
  File "<stdin>", line 2, in get_factorial
RecursionError: maximum recursion depth exceeded in comparison

默认情况下,函数调用深度的最大值为 1000,如果达到或者超过 1000 就会出现上面的错误信息。可以通过下面的代码来查看该系统的设置。

>>> import sys
>>> sys.getrecursionlimit()   # 得到最大调用深度
1000                    # 目前值为1000

如果希望修改该系统值,也可以通过 sys 模块的接口函数来实现。如希望最大函数调用深度为 10000,那么可以使用下面的代码进行修改:

>>> import sys
>>> sys.setrecursionlimit(10000)               # 设定最大调用深度

2、斐波拉契级数

有这样一个数列:1,1,2,3,5,8,13,21,34…。其第一元素和第二个元素等于 1,其他元素等于其前面两个元素的和。用数学公式表示如下:


可以用下面的代码来实现。

>>> def fab(n):          # 定义斐波拉契级数
...     if n in [1, 2]:  # 如果n=1或者2
...         return 1
...     return fab(n-1)+fab(n-2)    # n>2
...
>>> fab(1)                          # 斐波拉契级数的第一个元素
1
>>> fab(2)                          # 斐波拉契级数的第二个元素
1
>>> fab(8)                          # 斐波拉契级数的第8个元素
21
>>> fab(8)                          # 斐波拉契级数的第9个元素
34

3、全排列

对于一个输入的列表,可以通过改变元素的位置来得到不同的值。全排列就是得到所有的这些排列的列表。一般对于 n 个元素的列表有 n! 种排列方式。如对于 [1,2,3] 有下面几种排列方法:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

下面是用递归的方法实现的全排列。

>>> def sub_combination(left, right):  # left表示左边待处理的列表
...     if len(left) > 0:              # 如果没有处理完
...         for item in left:          # 从没有处理完的元素中取出一个
...             new_right = right + [item]      # 将该元素放入到处理好的列表中
...             new_left = [x for x in left if x != item]
...             sub_combination(new_left, new_right)    # 递归继续处理
...     else:                          # 所有元素都已经处理完毕
...         print(right)               # 显示这个排列的内容
...                                    # 结束sub_combination()的定义
>>> def combination(l):                # 已经处理的列表为空
...     return sub_combination(l, [])  # 开始处理
...                                    # 结束combination()的定义
>>> combination(["alex", "bob", "carol"])    # 对3个元素的列表进行排列
['alex', 'bob', 'carol']               # 排列结果,一行一个结果
['alex', 'carol', 'bob']
['bob', 'alex', 'carol']
['bob', 'carol', 'alex']
['carol', 'alex', 'bob']
['carol', 'bob', 'alex']


我要发帖
Python函数
2021-12-10 23:42:59加入圈子
  • 6

    条内容
函数是代码的基本模块,其完成某个特定的功能,可以被其他代码使用。函数能够提高代码的模块化程度,更加有效地组织代码,有利于协同开发。
现代软件开发语言都支持函数,我们可以认为函数是代码的最基本单元,即使是最简单的“Hello,python”代码也涉及调用函数 print()。
本章将介绍函数的基本概念和用法,包括 Python 函数的定义和使用、Python 函数参数的使用,常用的系统自带函数以及 lambda 函数和递归等方面的内容。