python - 将递归函数变成迭代函数

Question

我编写了以下递归函数，但由于最大递归深度而导致运行时错误。我想知道是否可以编写一个迭代函数来克服这个问题:

def finaldistance(n):

   if n%2 == 0:
       return 1 + finaldistance(n//2) 

   elif n != 1:
       a = finaldistance(n-1)+1
       b = distance(n)
       return min(a,b)

   else:
       return 0

我试过的是这个，但它似乎不起作用，

def finaldistance(n, acc):

   while n > 1:

     if n%2 == 0:
        (n, acc) = (n//2, acc+1)

     else:
        a = finaldistance(n-1, acc) + 1
        b = distance(n)
        if a < b:
          (n, acc) = (n-1, acc+1)

        else:
          (n, acc) =(1, acc + distance(n))

   return acc

Answer 1

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”方法；您可能会使用懒惰评估的列表推导式构建一个更紧凑、更易于理解的方法。此答案旨在回答提出的特定问题:我们通常如何将递归方法转换为迭代方法 ?

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