递归不是超级大国：迭代阿克曼
这篇文章有臭名昭著的递归 Ackermann 函数的 Python 代码，但没有使用递归。 许多人认为递归算法具有一些特殊的能力，可以进行迭代算法无法进行的计算。 但是递归不是超能力：递归能做的事没有循环和堆栈不能做的事。
这篇博文包含来自 Al Sweigart 的下一本书 The Recursive Book of Recurson 的信息，来自 No Starch Press。 该书将于 2022 年 2 月发行。您可以使用折扣代码 PREORDERRECURSION 享受预购 30% 的折扣，并在购买印刷书时免费获得电子书。 本书也将根据 Creative Commons 许可在 Invent with Python 网站上免费提供。 Al Sweigart 还在 North Bay Python 2018 上发表了题为“初学者递归：递归初学者指南”的递归会议演讲。
堆栈是计算中最简单的数据结构之一。 它像列表或数组一样存储多个值，但与列表或数组不同的是，它限制您只能在堆栈的“顶部”添加或删除值。 添加值称为将值压入堆栈，而删除值称为从堆栈弹出值。
调用堆栈是一种堆栈数据结构，您的编程语言的编译器或解释器使用它来跟踪函数调用完成时执行应该返回到程序中的哪个位置。 当你的程序调用一个函数时，这个返回地址信息被压入堆栈。 当函数调用返回时，信息从堆栈中弹出。 如果您的函数调用进行了一个函数调用，而该函数调用又进行了另一个函数调用，那么您会将三件事推入调用堆栈。
递归让初学者感到困惑，因为讲师和教程通常不会明确解释调用堆栈是什么。 调用堆栈由编译器或解释器在后台自动管理。 您不能像处理其他变量那样指向源代码中的某个位置并说“这是调用堆栈”。 这使得调用栈成为学生理解上的一个无形的鸿沟。
递归函数使用调用堆栈作为它们的堆栈数据结构，但您可以使用列表或数组作为堆栈数据结构，方法是限制自己只能从末尾添加或删除内容。 例如，Python 的 append() 和 pop() list 方法实际上是将 Python 列表视为堆栈的“push”和“pop”操作。
递归没有什么特别的。 你可以用递归做的任何事情都可以用循环和堆栈来完成。 此外，递归不会自动比迭代解决方案更“优雅”。 恰恰相反：与直接的迭代解决方案相比，递归通常会产生过度设计且可读性较差的代码。
为了证明这一点，我将使用著名的 Ackermann 递归函数作为示例。 除了极度递归的递归函数示例外，Ackermann 函数没有太多实际用途。 即使对该函数的小输入也可能导致需要数年或生命周期才能完成的大量计算。 这是 Python 中递归 Ackermann 函数的代码：
def ackermann(m, n):
if m == 0:
# BASE CASE
return n + 1
elif m > 0 and n == 0:
# RECURSIVE CASE
return ackermann(m - 1, 1)
elif m > 0 and n > 0:
# RECURSIVE CASE
return ackermann(m - 1, ackermann(m, n - 1))
例如，调用 ackermann(1, 1) 不到一秒钟即可完成。 呼唤 ackermann(4,1) 需要几分钟。 但是打电话 ackermann(15, 20) 将花费比宇宙存在时间更长的时间来完成计算。 阿克曼函数很快变得站不住脚。
但是递归不是超级大国。 甚至 Ackermann（递归函数中最递归的函数之一）也可以用循环和堆栈来编写。 这是 Python 中的迭代 Ackermann 实现：
print('Starting with m = 2, n = 3:')
callStack = [{'m': 2, 'n': 3, 'indentation': 0, 'instrPtr': 'start'}]
returnValue = None
while len(callStack) != 0:
m = callStack[-1]['m']
n = callStack[-1]['n']
indentation = callStack[-1]['indentation']
instrPtr = callStack[-1]['instrPtr']
if instrPtr == 'start':
print('%sackermann(%s, %s)' % (' ' * indentation, m, n))
if m == 0:
# BASE CASE
returnValue = n + 1
callStack.pop()
continue
elif m > 0 and n == 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after first recursive case'
callStack.append({'m': m - 1, 'n': 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif m > 0 and n > 0:
# RECURSIVE CASE
callStack[-1]['instrPtr'] = 'after second recursive case, inner call'
callStack.append({'m': m, 'n': n - 1, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after first recursive case':
returnValue = returnValue
callStack.pop()
continue
elif instrPtr == 'after second recursive case, inner call':
callStack[-1]['innerCallResult'] = returnValue
callStack[-1]['instrPtr'] = 'after second recursive case, outer call'
callStack.append({'m': m - 1, 'n': returnValue, 'indentation': indentation + 1, 'instrPtr': 'start'})
continue
elif instrPtr == 'after second recursive case, outer call':
returnValue = returnValue
callStack.pop()
continue
print(returnValue)
尝试运行这两个程序。 您会看到它们产生相同的输出。 但是迭代版本不使用递归函数。 事实上，它根本不使用函数：没有 def 程序中任意位置的语句。
如果您发现递归令人困惑或想知道为什么“应该”使用递归，请不要绝望。 递归是一种不合适的方法，它经常是合适的（甚至更多）。 请记住，递归虽然是每个程序员都应该了解的有用技术，但它并不是超能力。
如果您想了解如何使用递归，请查看 Al Sweigart 即将出版的书，No Starch Press 的 The Recursive Book of Recursion。 本书也将根据 Creative Commons 许可在 Invent with Python 网站上免费提供。 Al Sweigart 还在 North Bay Python 2018 上发表了题为“初学者递归：递归初学者指南”的递归会议演讲。
