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

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"方式; 你可以使用懒惰的评估列表推导建立一个更紧凑,易懂的方法.这个答案旨在回答所提到的具体问题: 我们一般如何将递归方法转换为迭代方法？

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

Answer 2

首先你需要找到 的所有值n，幸运的是你的序列是严格降序的并且仅取决于下一个距离：

values = []
while n > 1:
  values.append(n)
  n = n // 2 if n % 2 == 0 else n - 1

接下来您需要计算每个值的距离。为此，我们需要从底层开始：

values.reverse()

现在，如果我们需要计算下一个距离，我们可以轻松跟踪之前的距离。

distance_so_far = 0
for v in values:
  if v % 2 == 0:
    distance_so_far += 1
  else:
    distance_so_far = min(distance(v), distance_so_far + 1)

return distance_so_far

把它们放在一起：

def finaldistance(n):
    values = []
    while n > 1:
      values.append(n)
      n = n // 2 if n % 2 == 0 else n - 1

    values.reverse()
    distance_so_far = 0
    for v in values:
      if v % 2 == 0:
        distance_so_far += 1
      else:
        distance_so_far = min(distance(v), distance_so_far + 1)

    return distance_so_far

现在你使用的是内存而不是堆栈。

（我不用 Python 编程，所以这可能不是惯用的 Python）