1

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

我很难将以下 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
4

1 回答 1

2

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

尾递归和“常规”的区别

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

  1. 递归调用
  2. 一个记录返回值的地方。

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

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

  • 其他返回值
  • 拥有函数计算的结果

让我们看一个例子：

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]]]]

看到差异了吗？在“常规”递归调用中，返回函数递归地组成最终值。在尾递归中，他们只引用基本情况（最后一个评估）。我们称accumulator为跟踪旧值的参数。

递归模板

常规递归函数如下：

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-loop。

但不幸的是，Python 不是这些情况之一。当堆栈大于 1000 时，您将收到 RunTimeError。Guido先生 认为，由于尾调用优化（由抛出的帧引起）导致调试目的失去的清晰度比功能更重要。真可惜。Python 有很多很酷的功能性东西，尾递归在它之上会很棒：/

于 2013-10-28T00:39:39.837 回答