如何将递归转换为尾部递归

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）的值。如果我调用factorial（5），就在堆栈调用开始崩溃之前，我有：

^{pr2}$

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

一个尾部递归函数，将（2）放入它的参数中。

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

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

看到区别了吗？在“regular”递归调用中，返回函数递归地组成最终值。在尾部递归中，它们只引用基本情况（最后一个被评估的）。我们称累加器跟踪旧值的参数。在

递归模板

正则递归函数如下所示：

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

要在尾部递归中转换它，我们：

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

看：

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时，将出现运行时错误。Mr. Guido 认为由于尾部调用优化（由错误抛出的帧引起）导致的对调试目的的清晰性比特性更重要。真可惜。Python有很多很酷的函数，而尾部递归在它之上会很棒：/