python - 将递归函数转换为迭代函数

Johnbot 的解决方案向您展示了如何解决您的特定问题。一般来说，我们如何才能消除这种递归？让我通过一系列小的、明显正确、明显安全的重构来向您展示如何进行。

首先，这是您的函数的稍微重写的版本。我希望你同意它是一样的：

def f(n):
  if n % 2 == 0:
    return 1 + f(n // 2) 
  elif n != 1:
    a = f(n - 1) + 1
    b = d(n)
    return min(a, b)
  else:
    return 0

我希望基本情况是第一个。这个函数在逻辑上是一样的：

def f(n):
  if n == 1:
    return 0
  if n % 2 == 0:
    return 1 + f(n // 2) 
  a = f(n - 1) + 1
  b = d(n)
  return min(a, b)

我希望每次递归调用之后的代码都是方法调用，仅此而已。这些功能在逻辑上是相同的：

def add_one(n, x):
    return 1 + x

def min_distance(n, x):
    a = x + 1
    b = d(n)
    return min(a, b)

def f(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return add_one(n, f(n // 2))
    return min_distance(n, f(n - 1))

类似地，我们添加了计算递归参数的辅助函数：

def half(n):
    return n // 2

def less_one(n):
    return n - 1

def f(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return add_one(n, f(half(n))
    return min_distance(n, f(less_one(n))

同样，确保您同意该程序在逻辑上是相同的。现在我将简化参数的计算：

def get_argument(n):
    return half if n % 2 == 0 else less_one    

def f(n):
    if n == 1:
        return 0
    argument = get_argument(n) # argument is a function!
    if n % 2 == 0:
        return add_one(n, f(argument(n)))
    return min_distance(n, f(argument(n)))

现在我将对递归后的代码做同样的事情，我们将开始进行一次递归：

def get_after(n):
    return add_one if n % 2 == 0 else min_distance

def f(n):
    if n == 1:
        return 0
    argument = get_argument(n)
    after = get_after(n) # this is also a function!
    return after(n, f(argument(n)))

现在我注意到我们将 n 传递给 get_after，然后再次将它传递给“after”。我将使用这些函数来解决这个问题。 这一步很棘手。确保你理解它！

def add_one(n):
    return lambda x: x + 1

def min_distance(n):
    def nested(x):
        a = x + 1
        b = d(n)
        return min(a, b)
    return nested

这些函数确实有两个参数。现在他们接受一个参数，并返回一个接受一个参数的函数！所以我们重构了使用站点：

def get_after(n):
    return add_one(n) if n % 2 == 0 else min_distance(n)

和这里：

def f(n):
    if n == 1:
        return 0
    argument = get_argument(n)
    after = get_after(n) # now this is a function of one argument, not two
    return after(f(argument(n)))

同样，我们注意到我们正在调用get_argument(n)(n)以获取参数。让我们简化一下：

def get_argument(n):
    return half(n) if n % 2 == 0 else less_one(n)

让我们把它稍微笼统一点：

base_case_value = 0

def is_base_case(n):
  return n == 1

def f(n):
    if is_base_case(n):
        return base_case_value
    argument = get_argument(n)
    after = get_after(n)
    return after(f(argument))

好的，现在我们的程序非常紧凑。逻辑已经扩展到多个函数，其中一些是柯里化的，可以肯定的是。但是现在函数是这种形式，我们可以很容易地删除递归。这是真正棘手的一点是将整个事情变成一个显式堆栈：

def f(n):
    # Let's make a stack of afters. 
    afters = [ ]
    while not is_base_case(n) :
        argument = get_argument(n)
        after = get_after(n)
        afters.append(after)
        n = argument
    # Now we have a stack of afters:
    x = base_case_value
    while len(afters) != 0:
        after = afters.pop()
        x = after(x)
    return x

非常仔细地研究这个实现。你会从中学到很多东西。请记住，当您进行递归调用时：

after(f(something))

你是说那after是对. 我们通常通过将有关调用者代码中位置的信息放入“调用堆栈”来实现延续。我们在去除递归中所做的只是将延续信息从调用堆栈移到堆栈数据结构上。但信息完全一样。 f

这里要意识到的重要一点是，我们通常将调用堆栈视为“过去发生的什么事情让我来到这里？”。 那是完全倒退。调用堆栈会告诉你调用完成后你必须做什么！这就是我们在显式堆栈中编码的信息。当我们“展开堆栈”时，我们不会对每一步之前所做的事情进行编码，因为我们不需要这些信息。

正如我在最初的评论中所说：总有一种方法可以将递归算法转换为迭代算法，但这并不总是那么容易。我在这里向您展示了如何做到这一点：仔细重构递归方法，直到它非常简单。通过重构将其简化为单个递归。然后，并且只有在那时，应用此转换以将其转换为显式堆栈形式。 练习直到您对这个程序转换感到满意为止。然后，您可以继续使用更高级的技术来删除递归。

请注意，当然这几乎肯定不是解决这个问题的“pythonic”方式；您可能会使用延迟评估的列表推导构建一个更紧凑、更易于理解的方法。该答案旨在回答所提出的具体问题： 一般而言，我们如何将递归方法转换为迭代方法？

我在评论中提到删除递归的标准技术是将显式列表构建为堆栈。这表明了这种技术。还有其他技术：尾递归、连续传递风格和蹦床。这个答案已经太长了，所以我将在后续答案中介绍这些内容。

python - 将递归函数转换为迭代函数

问题描述

解决方案

推荐阅读