Python 中递归函数的 22 个示例

这篇博文包含来自 Al Sweigart 的下一本书 The Recursive Book of Recurson 的信息，来自 No Starch Press。 该书将于 2022 年 6 月发行。您可以使用折扣代码 PREORDERRECURSION 享受预购 30% 的折扣，并在购买印刷书时免费获得电子书。 本书也将根据 Creative Commons 许可在 Invent with Python 网站上免费提供。 Al Sweigart 还在 North Bay Python 2018 上发表了题为“初学者递归：递归初学者指南”的递归会议演讲。

这里有 22 个实际的、可运行的 Python 代码，用于几个递归函数，以一种初学者可以理解的风格编写，并产生可调试的输出。

这些不是代码片段； 它们是完整的、可运行的 Python 程序。 源代码已放在一个文本字段中，以便更轻松地滚动浏览这篇博文。 您可以单击文本字段，按 Ctrl-A 全选，然后按 Ctrl-C 将代码复制到剪贴板。 进入剪贴板后，您可以将其粘贴到编辑器或 IDE 中。 每个程序也有下载链接。

这些递归函数还旨在产生有用的、可教的输出。 一些功能有一个 indent 参数来帮助这个输出，而不是递归算法本身的一部分。

阿克曼

下载 ackermann.py

阿克曼函数以其发现者威廉·阿克曼 (Wilhelm Ackermann) 的名字命名。 Ackermann 是数学家 David Hilbert（希尔伯特曲线分形的创始人）的学生，他于 1928 年发表了他的函数。数学家 Rózsa Péter 和 Raphael Robinson 后来开发了本节中介绍的函数版本。 虽然阿克曼函数在高等数学中有一些应用，但它最广为人知的是作为高度递归函数的一个例子。 即使它的两个整数参数略有增加，也会导致它进行的递归调用次数大幅增加。

Computerphile YouTube 频道上有一个名为“最难计算的程序？”的视频。

def ackermann(m, n, indentation=None): 如果缩进为 None: indentation = 0 print(‘%sackermann(%s, %s)’ % (‘ ‘ * indentation, m, n)) if m == 0 : # BASE CASE return n + 1 elif m > 0 and n == 0: # RECURSIVE CASE return ackermann(m – 1, 1, indentation + 1) elif m > 0 and n > 0: # RECURSIVE CASE return ackermann(m – 1, ackermann(m, n – 1, indentation + 1), indentation + 1) print(‘从 m = 1, n = 1:’) print(ackermann(1, 1)) print(‘从 m 开始= 2, n = 3:’) 打印(阿克曼(2, 3))

该程序的输出如下所示：

从 m = 1, n = 1 开始：ackermann(1, 1) ackermann(1, 0) ackermann(0, 1) ackermann(0, 2) 3 从 m = 2, n = 3 开始：ackermann(2, 3 ) 阿克曼 (2, 2) 阿克曼 (2, 1) 阿克曼 (2, 0) 阿克曼 (1, 1) 阿克曼 (1, 0) 阿克曼 (0, 1) 阿克曼 (0, 2) 阿克曼 (1, 3) 阿克曼(1, 2) 阿克曼 (1, 1) 阿克曼 (1, 0) 阿克曼 (0, 1) 阿克曼 (0, 2) 阿克曼 (0, 3) 阿克曼 (0, 4) 阿克曼 (1, 5) 阿克曼 (1) , 4) 阿克曼 (1, 3) 阿克曼 (1, 2) 阿克曼 (1, 1) 阿克曼 (1, 0) 阿克曼 (0, 1) 阿克曼 (0, 2) 阿克曼 (0, 3) 阿克曼 (0, 4) ) 阿克曼 (0, 5) 阿克曼 (0, 6) 阿克曼 (1, 7) 阿克曼 (1, 6) 阿克曼 (1, 5) 阿克曼 (1, 4) 阿克曼 (1, 3) 阿克曼 (1, 2) 阿克曼(1, 1) 阿克曼 (1, 0) 阿克曼 (0, 1) 阿克曼 (0, 2) 阿克曼 (0, 3) 阿克曼 (0, 4) 阿克曼 (0, 5) 阿克曼 (0, 6) 阿克曼 (0 , 7) 阿克曼(0, 8) 9

二进制搜索

下载 binarySearch.py

二分搜索是一种通过重复确定项目位于列表的哪一半来在排序列表中定位目标项目的技术。搜索书架最公正的方法是从中间的一本书开始，然后确定是否您要查找的目标书在左半部分或右半部分。

然后你可以重复这个过程：看你选择的一半中间的书，然后确定你的目标书是在左边还是右边。 您可以这样做，直到您找到这本书或找到这本书应该在但不在的地方，并声明书架上不存在这本书。

def binarySearch(needle, haystack, left=None, right=None): # 默认情况下，`left` 和 `right` 都是 `haystack`: if left is None: left = 0 # `left` 默认为 0指数。 if right is None: right = len(haystack) – 1 # `right` 默认为最后一个索引。 打印（’搜索：’，干草堆[left:right + 1]) if left > right: # BASE CASE return None # `needle` 不在 `haystack` 中。 mid = (left + right) // 2 如果 needle == haystack[mid]: # BASE CASE return mid # 在 `haystack` 中找到了 `needle` elif needle haystack[mid]: # RECURSIVE CASE return binarySearch(needle, haystack, mid + 1, right) print(binarySearch(13, [1, 4, 8, 11, 13, 16, 19, 19]))

该程序的输出如下所示：

搜索： [1, 4, 8, 11, 13, 16, 19, 19]
搜索： [13, 16, 19, 19]
搜索： [13]
4个

组合

下载 combinations.py

给定一组项目，我们可以返回一组这些项目的每个组合。 例如，给定一组四个字母 ABCD，k 组合是：

0 组合和 4 组合有一个组合：分别是空字符串和 ABCD。 1-组合和3-组合分别有A、B、C、D和ABC、ABD、ACD、BCD四种组合。 2-组合最多的有六种组合：AB、AC、AD、BC、BD、CD。

def getCombos(chars, k, indent=0): debugMsg = ‘.’ * 缩进 + “In getCombos(‘” + chars + “‘, ” + str(k) + “)” print(debugMsg + ‘, start.’) if k == 0: # BASE CASE print(debugMsg + ” base案例回报 [”]“） 返回 [”] # 如果 k 要求 0 组合，则返回 ” 作为从 chars 中选择的零字母。 elif chars == ”: # BASE CASE print(debugMsg + ‘ base case returns []’） 返回 [] # 无论 k 是什么，空白字符都没有组合。 # 递归 CASE 组合 = []
# 第一部分，获取包含头部的组合：head = chars[:1]
尾巴=字符[1:]
print(debugMsg + ” part 1, get combos with head ‘” + head + “‘”) tailCombos = getCombos(tail, k – 1, indent + 1) 打印(‘.’ * indent + “Adding head ‘” + head + “‘ to tail combos:”) for tailCombo in tailCombos: print(‘.’ * indent + ‘New combination’, head + tailCombo) combinations.append(head + tailCombo) # 第二部分，获取不需要的组合包括头部： print(debugMsg + ” part 2, get combos without head ‘” + head + “‘)”) combinations.extend(getCombos(tail, k, indent + 1)) print(debugMsg + ‘ 结果是’, combinations) 返回组合 print(‘2-combinations of “ABC”:’) print(‘Results:’, getCombos(‘ABC’, 2))

该程序的输出如下所示：

“ABC”的 2 种组合：在 getCombos(‘ABC’, 2) 中，开始。 在 getCombos(‘ABC’, 2) 第 1 部分中，获取头部为 ‘A’ 的组合。在 getCombos(‘BC’, 1) 中，开始。 .在 getCombos(‘BC’, 1) 第 1 部分中，获取头部为 ‘B’ 的组合 ..在 getCombos(‘C’, 0) 中，开始。 ..在 getCombos(‘C’, 0) 基本情况返回 [”]
.将头部“B”添加到尾部组合： .新组合 B .在 getCombos(‘BC’, 1) 第 2 部分中，获得没有头部 ‘B’) 的组合 ..在 getCombos(‘C’, 1) 中，开始。 ..在 getCombos(‘C’, 1) 第 1 部分中，获取头部为 ‘C’ 的组合 …在 getCombos(”, 0) 中，开始。 …在 getCombos(”, 0) 基本情况返回 [”]
..将头部“C”添加到尾部组合：..新组合 C ..在 getCombos(‘C’, 1) 第 2 部分中，获取没有头部“C”的组合 …在 getCombos(”, 1) 中，开始。 …在 getCombos(”, 1) 基本情况返回 []
..在 getCombos(‘C’, 1) 结果是 [‘C’]
.In getCombos(‘BC’, 1) 结果是 [‘B’, ‘C’]
将头部“A”添加到尾部组合：新组合 AB 新组合 AC 在 getCombos(‘ABC’, 2) 第 2 部分中，获取没有头部“A”的组合。在 getCombos(‘BC’, 2) 中，开始。 .在 getCombos(‘BC’, 2) 第 1 部分中，获取头部为 ‘B’ 的组合 ..在 getCombos(‘C’, 1) 中，开始。 ..在 getCombos(‘C’, 1) 第 1 部分中，获取头部为 ‘C’ 的组合 …在 getCombos(”, 0) 中，开始。 …在 getCombos(”, 0) 基本情况返回 [”]
..将头部“C”添加到尾部组合：..新组合 C ..在 getCombos(‘C’, 1) 第 2 部分中，获取没有头部“C”的组合 …在 getCombos(”, 1) 中，开始。 …在 getCombos(”, 1) 基本情况返回 []
..在 getCombos(‘C’, 1) 结果是 [‘C’]
.将头部“B”添加到尾部组合： .新组合 BC .在 getCombos(‘BC’, 2) 第 2 部分中，获得没有头部 ‘B’) 的组合 ..在 getCombos(‘C’, 2) 中，开始。 ..在 getCombos(‘C’, 2) 第 1 部分中，获取头部为 ‘C’ 的组合 …在 getCombos(”, 1) 中，开始。 …在 getCombos(”, 1) 基本情况返回 []
..将头部“C”添加到尾部组合：..在 getCombos(‘C’, 2) 第 2 部分中，获取没有头部“C”的组合) …在 getCombos(”, 2) 中，开始。 …在 getCombos(”, 2) 基本情况返回 []
..在 getCombos(‘C’, 2) 结果是 []
.In getCombos(‘BC’, 2) 结果是 [‘BC’]
在 getCombos(‘ABC’, 2) 结果是 [‘AB’, ‘AC’, ‘BC’]
结果： [‘AB’, ‘AC’, ‘BC’]

倒计时

下载 countDownAndUp.py

此函数是一个简单递归函数的演示，并显示代码在递归调用前后的运行顺序。

def countDownAndUp(number): print(number) if number == 0: # BASE CASE print(‘Reached the base case.’) return else: # RECURSIVE CASE countDownAndUp(number – 1) print(number) 返回 countDownAndUp(3)

该程序的输出如下所示：

3 2 1 0 达到基本情况。 1 2 3

醉谢尔宾斯基三角

下载 drunkSierpinskiTriangle.py

这个程序使用 turtle 用于绘制谢尔宾斯基三角形分形的模块，除了有轻微的错误使分形看起来扭曲。

import random import turtle turtle.tracer(1000, 0) # 增加第一个参数来加速绘图。 turtle.setworldcoordinates(0, 0, 700, 700) turtle.hideturtle() MIN_SIZE = 4 # 尝试更改它以减少/增加递归量。 DRUNKENESS = 0.001 # 增加醉酒程度。 0.01 严重醉酒。 def midpoint(startx, starty, endx, endy): # 返回给定的四个参数中间的 x, y 坐标。 xDiff = abs(startx – endx) yDiff = abs(starty – endy) 返回 (min(startx, endx) + (xDiff / 2.0) + (random.random() * xDiff * (random.randint(-100, 100) *醉酒)), min(开始, 结束) + (yDiff / 2.0) + (random.random() * xDiff * (random.randint(-100, 100) * 醉酒))) def isTooSmall(ax, ay, bx , by, cx, cy): # 判断三角形是否太小无法绘制。 width = max(ax, bx, cx) – min(ax, bx, cx) height = max(ay, by, cy) – min(ay, by, cy) 返回宽度

该程序的输出如下所示：

八皇后

下载 eightQueens.py

八皇后难题是如何在棋盘上找到八个国际象棋皇后的排列，使他们不能互相攻击。 这个递归程序在 8 x 8 的棋盘上找到所有可能的解决方案。

SIZE = 8 def getPermutations(items): if len(items) == 0: # BASE CASE 返回 [[]]else: # 递归 CASE 排列 = []
头 = [items[0]]尾巴 = 物品[1:]
tailPermutations = getPermutations(tail) for tailPerm in tailPermutations: for i in range(len(tailPerm) + 1): newPermutation = tailPerm[0:i] + 头 + 尾Perm[i:]
permutations.append(newPermutation) 返回排列 def printBoard(board)：对于范围内的行（SIZE）：对于范围内的列（SIZE）：如果板[row] == column: print(‘Q’, end=”) # 打印 queen. else: print(‘. ‘, end=”) # 打印空格。 print() # 打印换行符。 print() numSolutions = 0 # 遍历所有可能的棋盘，每列有一个皇后，并 # 过滤掉皇后可以对角线攻击的棋盘： for board in getPermutations(list(range(SIZE))): # 检查是否任何皇后都可以对角线互相攻击 isValidBoard = True for row in range(SIZE): column = board[row]
for diagOffset in range(1, SIZE): if row + diagOffset = 0: # 边界检查。 如果（董事会[row – diagOffset] == 列 – diagOffset) 或 (board[row – diagOffset] == 列 + diagOffset): isValidBoard = False …

阅读更多