将递归函数更改为尾递归

Question

def singlesR(xs):
  if xs != [] :
    return  [[xs[0]]] + singlesR(xs[1:])
  else :
      return []

<递归函数>

如何改成尾递归函数？

#result value
singlesR([1,2,3,4]) == [[1], [2], [3], [4]]

Answer 1

如果你想用 tail-call 这个，你需要添加一个累加器：

def singlesR(xs, accumulator=[]):
    if not xs:
        return accumulator

    accumulator = accumulator + [xs[0]]
    return singlesR(xs[1:], accumulator)

请注意，现在 returning 之前的最后一次调用确实是对 singlesR.

的递归调用

但如评论中所述：由于 python 中没有 tail-call 优化，因此不会提高性能。

请注意，在您的版本中

return [[xs[0]]] + singlesR(xs[1:])

对 singlesR 的调用不在尾部位置 - 调用后有对 list.__add__.

的调用

Answer 2

正如评论中提到的和 this answer 中进一步讨论的那样 python 没有尾递归优化。

其他语言如 Haskell 支持尾递归。这个函数可以在 Haskell 中重写为尾递归函数，如下所示：

singlesR = singlesR' []
  where singlesR' acc [] = acc
        singlesR' acc (x:xs) = singlesR' ([x]:acc) xs

这里的主要观察结果是，在尾递归版本中，所有工作都在递归调用内部完成。

将递归函数更改为尾递归

change the recursive function to tail recursive

python

recursion

tail-recursion