在Python中删除递归

哈Ha！ 我向您介绍了Eric Lippert撰写的文章“在Python中删除递归，第1部分”的翻译。

在过去的20年中，尽管我从未真正使用过Python或对其进行过详细的研究，但我一直钦佩Python的简单性和强大功能。

最近，我仔细地看着他-原来这是一种非常不错的语言。

最近关于StackOverflow的一个问题使我想知道如何将递归算法转换为迭代算法，事实证明Python是一种非常好的语言。
问题的作者遇到的问题如下：

• 玩家位于编号字段上的任意单元格中；
• 目标是返回单元格编号1；
• 如果玩家在一个偶数正方形上，则他支付一个硬币，然后走到第一个单元格的一半。
• 如果玩家在一个奇数个方格上，他可以支付5个硬币并直接进入第一个方格，或者支付一个硬币并迈出第一步到第一个方格-在一个偶数方格上。

问题是：从当前单元格返回到第一个单元格，您需要支付的最少硬币数量是多少？

该任务有一个明显的递归解决方案：

def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5) 

但是，该程序崩溃了，达到了最大递归深度，这很可能是由于问题的作者尝试了很多数字这一事实。
因此，出现了一个问题：如何在Python中将递归算法转换为迭代算法？

在开始之前，我想指出，当然对于此特定问题有更快的解决方案，其本身并不是很有趣。

相反，此任务仅作为一般情况下如何摆脱Python程序中单个递归调用问题的起点。

关键是您可以转换任何简单的递归方法并摆脱递归，而这只是一个例子。

当然，我将展示的技术与Python的编写方式并不完全匹配，可能是Python风格的解决方案将使用生成器或该语言的其他功能。

我想在这里展示的是如何使用一系列小的安全转换来摆脱递归，从而将函数引向一种易于通过迭代替换递归的形式。

首先，让我们看看如何将程序转换为这种形式。

在转换的第一步中，我希望将递归调用之前执行的计算减少为参数的计算，而递归调用之后的计算应在接受递归调用结果的单独方法中执行。

 def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result) 

我要执行的第二步是在单独的函数中计算参数：

 # ... def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s <= 1: return 0 argument = get_argument(s) result = cost(argument) if s % 2 == 0: return add_one(result) return get_min(result) 

在第三步中，我想添加一个辅助函数，该函数将选择从递归返回后调用的继续函数。

请注意，辅助函数将返回一个函数。

 #... def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s <= 1: return 0 argument = get_argument(s) after = get_after(s) # after  ! result = cost(argument) return after(result) 

现在，我们以更一般和简洁的形式编写它：

 #... def is_base_case(s): return s <= 1 def base_case_value(s): return 0 def cost(s): if is_base_case(s): return base_case_value(s) argument = get_argument(s) after = get_after(s) return after(cost(argument)) 

可以看出，所做的每个更改都保留了程序的含义。

现在，对数字的奇偶校验执行两次，尽管在更改之前，只有一次校验。

如果需要，我们可以通过将两个辅助函数合并为一个返回元组的函数来解决此问题。

但是，让我们不必为此担心。

我们已经将递归方法简化为最通用的形式。

• 在基本情况下：
  
  • 计算要返回的值；
  • 归还它。
• 在非基本情况下：
  
  • 计算递归参数；
  • 进行递归调用；
  • 计算返回值；
  • 归还它。

在此步骤中需要注意的重要一点是，不应包含cost调用本身。

我在这里显示的方法删除了一个递归调用。

如果您有2个或更多的递归，那么我们需要一个不同的解决方案。

一旦将递归算法引入这种形式，就很容易将其转换为迭代式。

诀窍是想像一下递归程序中会发生什么。

我们如何进行递归下降：我们在递归调用之前调用get_argument，并在递归返回之后调用after函数。

也就是说，对get_argument的所有调用都在对after的所有调用之前发生。
因此，我们可以将其转换为2个周期：第一个调用get_argument并形成after函数的列表，第二个调用所有after函数：

 #... def cost(s): #     "after".    #       # ,    . afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument #       "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return result 

不再递归！

看起来像魔术，但是我们在此所做的所有工作与该程序的递归版本相同，并且顺序相同。

这个例子反映了我经常重复的关于调用栈的想法： 它的目的是传达下一步将发生的事情，而不是已经发生的事情！

在程序的递归版本中，调用堆栈上唯一有用的信息是after值，因为此函数将在下一步调用，而堆栈上的所有其他内容都不重要。

我们可以简单地存储after函数堆栈，而不是使用调用堆栈作为存储after堆栈的低效且繁琐的方式。

下次，我们将介绍一种更复杂的方法来删除Python中的递归。