时间戳

首页 > 解决方案 > 将具有两个连续“尾”递归调用的函数转换为迭代函数

loops - 将具有两个连续“尾”递归调用的函数转换为迭代函数

问题描述

我已经看到了很多关于如何在最后将带有单个递归调用的函数转换为迭代版本的示例；但是，如果最后有两个递归调用呢？

这是我的意思的一个例子，在 Python 中：

def doit(x, y, L):
  if x < y:
    x += 1
  else:
    x -= 1
    y -= 1
  if y > 0:
    L.append(x)
    doit(x, y, L)
    doit(x - 1, y - 1, L)

#usage
L = []
doit(3, 5, L)
print(L)

请注意，两个递归调用都在最后。不管我在这两个递归调用之前在代码中做什么，是否有一种通用方法可以将这样的东西转换为迭代版本？请记住，我上面提供的只是一个示例。

标签： loopsrecursionstackiteration

解决方案

不，没有针对尾递归情况的通用且简单的方法。即使您最后有 1 个递归调用，但该函数不是尾递归（例如return 5+foo(x)），这也是正确的。您必须显式维护一个堆栈，然后它甚至适用于最后有两个以上递归调用的情况。

要了解原因，请注意尾递归函数中的每个变量（即参数和局部变量）在任何给定时刻最多只能有一个可能的值。因此，您永远不需要在 RAM 中维护多个版本。因为在进行下一次递归调用时，一个好的编译器会销毁它们当前的版本并在它们当前所在的同一位置分配新版本。所以它基本上只是修改一个变量而不是分配新的变量。

因此，对于没有“最大 1 版本”保证的普通递归函数，请在主循环之前声明一个堆栈。其中的每个元素都是所有参数的元组。在循环内部，获取堆栈的最后一个元素（并从堆栈中删除它）。然后只需在循环内复制/粘贴您的函数体。但是，除了进行下一次递归调用外，创建一个包含该调用的所有参数值的元素并将其压入堆栈。您的代码已修改：

A = [] #your initial 'L'
stack = [(2,4,A)] #push values of initial call
while stack:
    x,y,L = stack.pop()
    print(x,y)
    if x < y:
        x += 1
    else:
        x -= 1
        y -= 1
    if y > 0:
        L.append(x)
        stack.append((x, y, L))
        stack.append((x - 1, y - 1, L))

但是，只有当递归调用的顺序无关紧要时，他才会起作用，比如 dfs。否则，我对“内部堆栈”有一个想法，但这个答案已经太长了。

推荐阅读