python - 如何将递归转换为尾递归

Question

是否总是可以将递归转换为尾递归？

我很难将以下 Python 函数转换为尾递归函数。

def BreakWords(glob):
  """Break a string of characters, glob, into a list of words.

  Args:
    glob: A string of characters to be broken into words if possible.

  Returns:
    List of words if glob can be broken down. List can be empty if glob is ''.
    None if no such break is possible.
  """
  # Base case.
  if len(glob) == 0:
    return []

  # Find a partition.
  for i in xrange(1, len(glob) + 1):
    left = glob[:i]
    if IsWord(left):
      right = glob[i:]
      remaining_words = BreakWords(right)
      if remaining_words is not None:
        return [left] + remaining_words

  return None

Answer 1

我不确定是否总是如此，但大多数递归函数都可以实现为尾递归。此外，尾递归与尾递归优化不同。

尾递归和“常规”递归的区别

递归函数中必须存在两个元素:

1. 递归调用
2. 用于记录返回值的位置。

“常规”递归函数将 (2) 保留在堆栈帧中。

常规递归函数的返回值由两种类型的值组成:

• 其他返回值
• owns函数计算结果

让我们看一个例子:

def factorial(n):
    if n == 1 return 1
    return n * factorial(n-1)

例如，框架 f(5) “存储”其自身计算的结果 (5) 和 f(4) 的值。如果我调用阶乘(5)，就在堆栈调用开始崩溃之前，我有:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

请注意，除了我提到的值之外，每个堆栈还存储函数的整个范围。因此，递归函数 f 的内存使用量为 O(x)，其中 x 是我必须进行的递归调用的次数。因此，如果我需要 1kb RAM 来计算阶乘 (1) 或阶乘 (2)，则需要 ~100k 来计算阶乘 (100)，依此类推。

尾递归函数将 (2) 放入其参数中。

在尾递归中，我使用参数将每个递归帧中部分计算的结果传递到下一个递归帧。让我们看看阶乘示例，尾递归:

def factorial(n):
    def tail_helper(n, acc):
        if n == 1 or n == 2: return acc
        return tail_helper(n-1, acc + n)
return tail_helper(n,0)

让我们看看它的阶乘(4)中的框架:

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

看到差异了吗？ 在“常规”递归调用中，返回函数递归地组成最终值。在尾递归中，它们仅引用基本情况(最后一个评估的情况)。我们将累加器称为跟踪旧值的参数。

递归模板

常规的递归函数如下:

def regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

为了将其转换为尾递归，我们:

• 引入一个携带累加器的辅助函数
• 在主函数内运行辅助函数，并将累加器设置为基本情况。

看:

def tail(n):
    def helper(n, accumulator):
        if n == base case:
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

你的例子:

我做了这样的事情:

def BreakWords(glob):
    def helper(word, glob, acc_1, acc_2):
        if len(word) == 0 and len(glob) == 0:
            if not acc_1:
                return None
            return acc
        if len(word) == 0:
            word = glob.pop[0]
            acc_2 = 0

        if IsWord(word.substring[:acc_2]):
            acc_1.append(word[:acc_2])
            return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

        return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

    return helper("", glob, [], 0)

为了消除您所做的 for 语句，我使用 2 个累加器执行了递归辅助函数。一个用于存储结果，一个用于存储我当前正在尝试的位置。

尾部调用优化

由于尾​​部调用堆栈的非边界情况中没有存储任何状态，因此它们并不那么重要。然后，某些语言/解释器用新堆栈替换旧堆栈。因此，由于没有堆栈帧限制调用次数，尾部调用的行为就像 for 循环。

但不幸的是，Python 并不是这些情况之一。当堆栈大于 1000 时，您将收到 RunTimeError。 Mr. Guido 认为由于尾部调用优化(由帧抛出错误引起)而导致调试目的的清晰度损失比该功能更重要。太可惜了。 Python 有很多很酷的函数式东西，尾递归在它之上会很棒:/