题 什么是尾递归?


在开始学习口齿不清时,我遇到了这个词 尾递归。这究竟是什么意思?


1296
2017-08-31 18:21


起源


对于好奇:无论是在这段时间还是在语言中已经很长时间了。虽然在古英语中使用;同时也是一个中古英语的发展。作为连词,它们在意义上是可以互换的,但是却没有在标准的美式英语中存活下来。 - Filip Bartuzi
也许它已经晚了,但这篇关于尾递归的文章非常好:programmerinterview.com/index.php/recursion/tail-recursion - Sam003
首先,您需要了解递归。一个很好的评论解释它在这里: stackoverflow.com/questions/33923/... - joe_young
识别尾递归函数的一大好处是可以将其转换为迭代形式,从而从算法堆栈开销中重新获得算法。可能会访问@Kyle Cronin和下面的其他几个人的回复 - KGhatak
@joe_young - 递归神奇的故事。我无法对你的评论进行足够的评价。好的! - RBT


答案:


考虑一个添加前N个整数的简单函数。 (例如。 sum(5) = 1 + 2 + 3 + 4 + 5 = 15)。

这是一个使用递归的简单JavaScript实现:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

如果你打过电话 recsum(5),这是JavaScript解释器将评估的内容:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

请注意每个递归调用必须在JavaScript解释器开始实际执行计算总和之前完成。

这是同一函数的尾递归版本:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

这是您调用时将发生的事件序列 tailrecsum(5),(这实际上是 tailrecsum(5, 0),因为默认的第二个参数)。

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归的情况下,每次递归调用的评估, running_total 已更新。

注意:原始答案使用了Python中的示例。由于现代JavaScript解释器支持,因此已将其更改为JavaScript 尾调用优化 但Python解释器却没有。


1294
2017-08-29 03:57



Python在这里是一个奇怪的选择,因为它没有AFAIK尾递归消除。 - Chris Conway
克里斯康威是对的。遗憾的是,尾部调用没有在Python中进行优化。 Guido声称可用于调试的堆栈优于TCO。 - McPherrinM
你会发现Guido的意见 这里。 - new123456
@Paco,链接是什么?这是一种玩笑吗?这是404,你有镜子吗? :-) - tillda
@tillda:是个笑话。这是一面镜子: cs.cmu.edu/~wklieber/python-tail-recursion.jpg - Paco


传统的递归,典型的模型是先执行递归调用,然后获取递归调用的返回值并计算结果。以这种方式,在每次递归调用返回之前,您不会得到计算结果。

尾递归,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用的形式 (return (recursive-function params))基本上,任何给定递归步骤的返回值与下一个递归调用的返回值相同

这样做的结果是,一旦准备好执行下一个递归步骤,就不再需要当前的堆栈帧了。这允许一些优化。实际上,使用适当编写的编译器,您永远不应该有堆栈溢出 暗笑 尾递归调用。只需重复使用当前堆栈帧进行下一个递归步骤。我很确定Lisp会这样做。


547
2017-08-31 17:29



“我很确定Lisp会这样做” - Scheme确实如此,但Common Lisp并不总是如此。 - Aaron
@Daniel“基本上,任何给定递归步骤的返回值都与下一个递归调用的返回值相同。” - 我没有看到这个参数对于Lorin Hochstein发布的代码片段是正确的。你能详细说明吗? - Geek
@Geek这是一个非常晚的回应,但在Lorin Hochstein的例子中确实如此。每个步骤的计算在递归调用之前完成,而不是在它之后完成。因此,每个停靠点只是直接从上一步返回值。最后一个递归调用完成计算,然后在调用堆栈中一直返回未修改的最终结果。 - reirab
Scala但是你需要指定@tailrec来强制执行它。 - SilentDirge
“通过这种方式,在每次递归调用返回之前,您不会得到计算结果。” - 也许我误解了这一点,但对于懒惰的语言来说,这并不是特别正确的 传统的递归 是实际获得结果而不调用所有递归的唯一方法(例如,用&&折叠无限的Bools列表)。 - hasufell


重要的一点是尾递归基本上等于循环。这不仅仅是编译器优化的问题,而是表达性的基本事实。这有两种方式:你可以采取任何形式的循环

while(E) { S }; return Q

哪里 E 和 Q 是表达和 S 是一系列语句,并将其转换为尾递归函数

f() = if E then { S; return f() } else { return Q }

当然, ES,和 Q 必须定义为计算某些变量的一些有趣值。例如,循环功能

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

相当于尾递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(使用具有较少参数的函数对尾递归函数进行“包装”是一种常见的功能习惯。)


165
2017-08-29 16:03



很好的解释,但为什么你的函数叫做fibo?那不是斐波那契;它的f(n)=二项式(n + 1,2) - RexE
@RexE全脑屁。我投了20次,没人指出来! - Chris Conway
:)还要确保重命名递归调用。 - RexE
在@LorinHochstein的回答中,根据他的解释,我理解尾递归是当递归部分跟随“返回”时,然而在你的情况下,尾递归不是。你确定你的例子被正确地考虑了尾递归吗? - CodyBugstein
@Imray尾部递归部分是sum_aux中的“return sum_aux”语句。 - Chris Conway


摘自本书 Lua编程 节目 如何进行正确的尾递归 (在Lua中,但也应该适用于Lisp)以及为什么它更好。

一个 尾巴电话 [tail recursion]是一种goto打扮   作为电话。当a时发生尾调用   函数将另一个称为最后一个   行动,所以它没有别的办法。   例如,在以下代码中,   打电话给 g 是一个尾调:

function f (x)
  return g(x)
end

f 电话 g,它没有别的   去做。在这种情况下,该计划   不需要返回调用   函数调用时的函数   结束。因此,尾调用后,   该计划不需要保留任何   有关调用功能的信息   在堆栈中。 ...

因为正确的尾调用不   堆栈空间,没有限制   “嵌套”尾部调用的数量a   程序可以。例如,我们可以   用any调用以下函数   数字作为参数;永远不会   溢出堆栈:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

......正如我之前所说,尾部呼叫是一个   转发。因此,非常有用   应用适当的尾调用   Lua用于编程状态机。   这样的应用可以代表每个   以功能陈述;改变国家   是去(或打电话)具体的   功能。举个例子,让我们来吧   考虑一个简单的迷宫游戏。迷宫   有几个房间,每个房间最多   四扇门:北,南,东,和   西方。在每一步,用户输入一个   运动方向。如果有门   在那个方向,用户去   相应的房间;否则,   程序打印警告。目标是   从最初的房间到决赛   房间。

这个游戏是一个典型的状态机,   当前房间是州。   我们可以用一个实现这样的迷宫   每个房间的功能。我们用尾巴   打电话从一个房间搬到   另一个。一个有四个房间的小迷宫   可能看起来像这样:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

所以你看,当你做一个递归调用,如:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾递归,因为在进行递归调用之后,您仍然可以在该函数中执行操作(添加1)。如果输入一个非常高的数字,它可能会导致堆栈溢出。


110
2017-08-29 03:55



这是一个很好的答案,因为它解释了尾调用对堆栈大小的影响。 - Andrew Swan
@AndrewSwan的确,虽然我相信最初的提问者和偶尔会发现这个问题的读者可能会更好地接受所接受的答案(因为他可能不知道堆栈实际上是什么。)顺便说一句,我使用Jira,大风扇。 - Hoffmann
我最喜欢的答案也包括对堆栈大小的影响。 - njk2015


使用常规递归,每个递归调用将另一个条目推送到调用堆栈。递归完成后,应用程序必须将每个条目一直弹回。

使用尾递归,编译器能够将堆栈折叠为一个条目,因此您可以节省堆栈空间...大型递归查询实际上可能导致堆栈溢出。

基本上Tail递归可以优化为迭代。


57
2017-08-29 03:57





这是一个例子,而不是用文字解释。这是阶乘函数的Scheme版本:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

这是一个尾递归的阶乘版本:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

您将在第一个版本中注意到对事实的递归调用被送入乘法表达式,因此在进行递归调用时必须将状态保存在堆栈中。在尾递归版本中,没有其他S表达式等待递归调用的值,并且由于没有进一步的工作要做,因此不必将状态保存在堆栈中。通常,Scheme尾递归函数使用常量堆栈空间。


56
2017-08-29 07:21



+1用于提及尾递归的最重要方面,它们可以转换为迭代形式,从而将其转换为O(1)内存复杂形式。 - KGhatak
@KGhatak并不完全;答案正确地讲述了“恒定堆栈空间”,而不是一般的内存。不要挑剔,只是为了确保没有误解。例如尾递归列表尾变异 list-reverse 过程将在常量堆栈空间中运行,但将在堆上创建和增长数据结构。树遍历可以在另一个参数中使用模拟堆栈。等等 - Will Ness


行话文件有关于尾递归定义的说法:

尾递归 /n./

如果你还没有厌倦它,请参阅尾递归。


52
2017-08-29 03:57



我看到你在那里做了什么。那里有厚颜无耻的例子。 :d - Sajib Acharya
这篇文章的喜剧增值和赞成补偿了这不是答案的事实。 - Eric Leschinski
我,说真的, 没有看到这一点。 - Mehraj Malik


尾递归是指递归调用在递归算法的最后一条逻辑指令中的最后一次。

通常在递归中你有一个 基本情况 这是什么停止递归调用并开始弹出调用堆栈。使用一个经典的例子,虽然比Lisp更多的C-ish,但是阶乘函数说明了尾递归。发生递归调用  检查基本情况。

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

注意,对factorial的初始调用必须是阶乘(n,1),其中n是要计算阶乘的数字。


23
2017-08-31 23:52





这意味着您不必将指令指针推到堆栈上,只需跳转到递归函数的顶部并继续执行即可。这允许函数无限递归,而不会溢出堆栈。

我写了一篇 博客 在主题上发布,其中包含堆栈帧的图形示例。


20
2017-10-14 21:20





这是一个比较两个函数的快速代码片段。第一种是传统递归,用于查找给定数字的阶乘。第二个使用尾递归。

理解起来非常简单直观。

判断递归函数是否为尾递归的简单方法是,它是否在基本情况下返回具体值。意味着它不会返回1或true或类似的东西。它将更可能返回一个方法参数的某些变体。

另一种方法是判断递归调用是否没有任何添加,算术,修改等等...意味着它只是一个纯粹的递归调用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

13
2017-10-01 22:06



0!是1.所以“mynumber == 1”应该是“mynumber == 0”。 - polerto


在Java中,这里有一个可能的Fibonacci函数的尾递归实现:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

将此与标准递归实现进行对比:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

10
2017-08-29 03:50



这对我来说是错误的结果,因为输入8我得到36,它必须是21.我错过了什么?我正在使用java并复制粘贴它。 - Alberto Zaccagni
这将在[1,n]中返回i的SUM(i)。与Fibbonacci无关。对于Fibbo,您需要进行减法测试 iter 至 acc 什么时候 iter < (n-1)。 - Askolein