什么是尾递归？

23 回答

• 4

  在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);
  }
  

  回复于 2024-05-03T06:12:08+08:00
• 11

  考虑一个添加前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解释器支持tail call optimization但Python解释器不支持 .

  回复于 2024-05-03T06:12:08+08:00
• 4

  “Lua编程”一书的摘录显示how to make a proper tail recursion（在Lua中，但也应该适用于Lisp）以及为什么它更好 .

  尾部调用[tail recursion]是一种打扮成呼叫的goto . 当函数调用另一个函数作为其最后一个动作时，会发生尾调用，因此它没有其他任何操作 . 例如，在下面的代码中，对g的调用是尾调用：函数f（x）
  返回g（x）
  结束
  在f调用g之后，它没有别的事可做 . 在这种情况下，当被调用函数结束时，程序不需要返回调用函数 . 因此，在尾调用之后，程序不需要保留有关堆栈中调用函数的任何信息 . ...因为正确的尾调用不使用堆栈空间，所以程序可以进行的“嵌套”尾调用的数量没有限制 . 例如，我们可以使用任何数字作为参数调用以下函数;它永远不会溢出堆栈：function foo（n）
  如果n> 0则返回foo（n - 1）结束
  结束
  ......正如我之前所说，尾调用是一种转向 . 因此，Lua中正确尾部调用的一个非常有用的应用是编程状态机 . 这些应用程序可以通过函数表示每个状态;改变状态是去（或调用）一个特定的功能 . 举个例子，让我们考虑一个简单的迷宫游戏 . 迷宫有几个房间，每个房间最多有四扇门：北，南，东和西 . 在每个步骤，用户输入移动方向 . 如果在该方向上有门，则用户前往相应的房间;否则，程序会打印警告 . 目标是从最初的房间到最后的房间 . 这个游戏是一个典型的状态机，当前的房间是状态 . 我们可以为每个房间实现一个功能的迷宫 . 我们使用尾调用从一个房间移动到另一个房间 . 一个有四个房间的小迷宫看起来像这样：function room1（）
  local move = io.read（）
  如果move ==“south”则返回room3（）
  elseif move ==“east”然后返回room2（）
  否则打印（“无效移动”）
  返回room1（） - 住在同一个房间
  结束
  结束

  功能室2（）
  local move = io.read（）
  如果移动==“南”然后返回room4（）
  elseif move ==“west”然后返回room1（）
  否则打印（“无效移动”）
  返回room2（）
  结束
  结束

  功能室3（）
  local move = io.read（）
  如果move ==“north”则返回room1（）
  elseif move ==“east”然后返回room4（）
  否则打印（“无效移动”）
  返回room3（）
  结束
  结束

  功能室4（）
  打印（ “祝贺你！”）
  结束

  所以你看，当你做一个递归调用，如：

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

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

  回复于 2024-05-03T06:12:08+08:00
• 8

  为了理解尾调用递归和非尾调用递归之间的一些核心差异，我们可以探索这些技术的.NET实现 .

  这篇文章包含C＃，F＃和C \ CLI中的一些示例：Adventures in Tail Recursion in C#, F#, and C++\CLI .

  C＃不优化尾调用递归，而F＃则优化 .

  原理的差异涉及循环与Lambda演算 . C＃的设计考虑了循环，而F＃是根据Lambda演算的原理构建的 . 有关Lambda演算原理的非常好（且免费）的书，请参阅Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman .

  关于F＃中的尾调用，有关非常好的介绍性文章，请参阅Detailed Introduction to Tail Calls in F# . 最后，这篇文章介绍了非尾递归和尾调用递归（在F＃中）之间的区别：Tail-recursion vs. non-tail recursion in F sharp .

  如果您想了解C＃和F＃之间尾调用递归的一些设计差异，请参阅Generating Tail-Call Opcode in C# and F# .

  如果您非常关心要知道哪些条件阻止C＃编译器执行尾调用优化，请参阅以下文章：JIT CLR tail-call conditions .

  回复于 2024-05-03T06:12:08+08:00
• 4

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

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

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

  回复于 2024-05-03T06:12:08+08:00
• 15

  我不是Lisp程序员，但我认为this会有所帮助 .

  基本上它是一种编程风格，使得递归调用是你做的最后一件事 .

  回复于 2024-05-03T06:12:08+08:00
• 2

  尾递归是你现在的生活 . 你不断地循环使用相同的堆栈帧，因为没有理由或方法可以返回到“之前的”帧 . 过去已经完成，所以它可以被丢弃 . 你得到一个框架，永远移动到未来，直到你的过程不可避免地死亡 .

  当你考虑某些进程可能会使用额外的帧但是如果堆栈没有无限增长时仍然被认为是尾递归的话，这个类比就会崩溃 .

  回复于 2024-05-03T06:12:08+08:00
• 3

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

  理解起来非常简单直观 .

  判断递归函数是否为尾递归的简单方法是它是否在基本情况下返回具体值 . 意味着它不会返回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);
      }
  }
  

  回复于 2024-05-03T06:12:08+08:00
• 3

  这是关于尾递归的Structure and Interpretation of Computer Programs的摘录 .

  在对比迭代和递归中，我们必须注意不要将递归过程的概念与递归过程的概念混淆 . 当我们将过程描述为递归时，我们指的是过程定义（直接或间接）引用过程本身的语法事实 . 但是，当我们将流程描述为遵循线性递归的模式时，我们会谈论流程如何演变，而不是关于如何编写流程的语法 . 我们将一个递归过程（例如fact-iter）称为生成迭代过程似乎令人不安 . 但是，这个过程确实是迭代的：它的状态完全被它的三个状态变量捕获，并且解释器需要只跟踪三个变量才能执行该过程 . 过程和过程之间的区别可能令人困惑的一个原因是，大多数常见语言（包括Ada，Pascal和C）的实现都是以这样的方式设计的，即任何递归过程的解释都会消耗大量的内存 . 过程调用的数量，即使所描述的过程原则上是迭代的 . 因此，这些语言只能通过使用特殊用途的“循环结构”来描述迭代过程，例如do，repeat，until，for和while . Scheme的实现不会分享这个缺陷 . 它将在常量空间中执行迭代过程，即使迭代过程由递归过程描述 . 具有此属性的实现称为tail-recursive . 使用尾递归实现，可以使用普通过程调用机制表示迭代，因此特殊迭代构造仅作为语法糖使用 .

  回复于 2024-05-03T06:12:08+08:00
• 8

  这是一个Common Lisp示例，它使用尾递归来执行阶乘 . 由于无堆栈特性，人们可以执行疯狂的大因子计算......

  (defun ! (n &optional (product 1))
      (if (zerop n) product
          (! (1- n) (* product n))))
  

  然后为了好玩你可以尝试 (format nil "~R" (! 25))

  回复于 2024-05-03T06:12:08+08:00
• 59

  这个问题有很多很好的答案......但是我不得不提出如何定义"tail recursion"，或者至少"proper tail recursion."的另一种看法 . 即：应该把它看作程序中特定表达式的属性吗？或者应该将其视为编程语言实现的属性？

  有关后一种观点的更多信息，Will Clinger，"Proper Tail Recursion and Space Efficiency"（PLDI 1998）的经典paper将"proper tail recursion"定义为编程语言实现的属性 . 构造定义是为了允许忽略实现细节（例如调用堆栈是否实际通过运行时堆栈或通过堆分配的链接帧列表来表示） .

  为了实现这一点，它使用渐近分析：不是通常看到的程序执行时间，而是程序空间使用 . 这样，堆分配的链表与运行时调用栈的空间使用最终是渐近等价的;所以人们可以忽略那种编程语言的实现细节（这个细节在实践中确实很重要，但是当人们尝试确定给定的实现是否满足要求"property tail recursive"）

  该论文值得仔细研究，原因如下：

  • 它给出了程序尾部表达式和尾部调用的归纳定义 . （这样的定义，以及为什么这些呼叫很重要，似乎是这里给出的大多数其他答案的主题 . ）

  以下是这些定义，只是为了提供文本的味道：

  定义1以核心方案编写的程序的尾部表达式归纳定义如下 . lambda表达式的主体是尾部表达式If（如果E0 E1 E2）是尾部表达式，则E1和E2都是尾部表达式 . 没有别的东西是尾巴表达 . 定义2尾调用是一个尾部表达式，它是一个过程调用 .

  （尾递归调用，或者正如文章所说，“自尾调用”是尾调用的特例，其中自己调用过程 . ）

  • 它为六个不同的"machines"提供了用于评估核心方案的正式定义，其中每个机器具有相同的可观察行为，除了每个机器所处的渐近空间复杂度类 .

  例如，在为机器定义后，分别为：1 . 基于堆栈的内存管理，2 . 垃圾收集，但没有尾调用，3 . 垃圾收集和尾调用，本文继续介绍更高级的存储管理策略，如4. "evlis tail recursion"，其中不需要在尾部调用中的最后一个子表达式参数的评估中保留环境，5 . 将闭包的环境简化为该闭包的自由变量，并且6. so-由Appel and Shao定义的"safe-for-space"语义 .

  • 为了证明这些机器实际上属于六个不同的空间复杂性类别，对于每对比较的机器，本文提供了一些程序的具体示例，这些程序将在一台机器上暴露渐近空间而不在另一台机器上 .

  ---

  （现在阅读我的答案，我'm not sure if I' m设法实际捕获了Clinger paper的关键点 . 但是，唉，我现在不能把更多的时间用于开发这个答案 . ）

  回复于 2024-05-03T06:12:08+08:00
• 173

  简而言之，尾递归具有递归调用作为函数中的 last 语句，因此它不必等待递归调用 .

  所以这是一个尾递归，即N（x - 1，p * x）是函数中的最后一个语句，编译器很聪明地知道它可以被优化为for循环（factorial） . 第二个参数p带有中间产品值 .

  function N(x, p) {
     return x == 1 ? p : N(x - 1, p * x);
  }
  

  这是编写上述阶乘函数的非尾递归方式（尽管有些C编译器可能无论如何都能优化它） .

  function N(x) {
     return x == 1 ? 1 : x * N(x - 1);
  }
  

  但这不是：

  function F(x) {
    if (x == 1) return 0;
    if (x == 2) return 1;
    return F(x - 1) + F(x - 2);
  }
  

  我写了一篇名为“Understanding Tail Recursion – Visual Studio C++ – Assembly View”的长篇文章

  

  回复于 2024-05-03T06:12:08+08:00
• 26

  递归意味着一个函数调用自身 . 例如：

  (define (un-ended name)
    (un-ended 'me)
    (print "How can I get here?"))
  

  Tail-Recursion表示结束函数的递归：

  (define (un-ended name)
    (print "hello")
    (un-ended 'me))
  

  看，最后一个未结束的函数（过程，在方案术语中）做的是调用自身 . 另一个（更有用）的例子是：

  (define (map lst op)
    (define (helper done left)
      (if (nil? left)
          done
          (helper (cons (op (car left))
                        done)
                  (cdr left))))
    (reverse (helper '() lst)))
  

  在辅助程序中，如果左边不是nil，它会做的最后一件事就是自己调用（事后有些东西和cdr的东西） . 这基本上是您映射列表的方式 .

  尾递归具有很大的优势，解释器（或编译器，依赖于语言和供应商）可以优化它，并将其转换为等同于while循环的东西 . 事实上，在Scheme传统中，大多数“for”和“while”循环是以尾递归的方式完成的（据我所知，没有for和while） .

  回复于 2024-05-03T06:12:08+08:00
• 10

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

  tail recursion /n./

  如果你还没有厌倦它，请参阅尾递归 .

  回复于 2024-05-03T06:12:08+08:00
• 7

  我理解 tail call recursion 的最好方法是递归的特例，其中 last call （或尾调用）就是函数本身 .

  比较Python中提供的示例：

  def recsum(x):
   if x == 1:
    return x
   else:
    return x + recsum(x - 1)
  

  ^递推

  def tailrecsum(x, running_total=0):
    if x == 0:
      return running_total
    else:
      return tailrecsum(x - 1, running_total + x)
  

  ^ TAIL RECURSION

  正如您在常规递归版本中所看到的，代码块中的最终调用是 x + recsum(x - 1) . 因此在调用 recsum 方法之后，还有另一个操作 x + .. .

  但是，在尾递归版本中，代码块中的最终调用（或尾调用）是 tailrecsum(x - 1, running_total + x) ，这意味着最后一次调用方法本身并且之后没有操作 .

  这一点很重要，因为这里看到的尾递归并没有使内存增长，因为当底层VM看到一个函数调用自身处于尾部位置（在函数中要计算的最后一个表达式）时，它会消除当前的堆栈帧，被称为尾部呼叫优化（TCO） .

  编辑

  NB . 请记住，上面的示例是用Python编写的，其运行时不支持TCO . 这只是一个例子来解释这一点 . Scheme，Haskell等语言支持TCO

  回复于 2024-05-03T06:12:08+08:00
• 60

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

  while(E) { S }; return Q
  

  其中 E 和 Q 是表达式， S 是一个语句序列，并将其转换为尾递归函数

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

  当然，必须定义 E ， S 和 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);
  }
  

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

  回复于 2024-05-03T06:12:08+08:00
• 582

  递归有两种基本类型： head recursion 和 tail recursion.

  在头递归中，函数进行递归调用，然后执行更多计算，例如，可能使用递归调用的结果 . 在尾递归函数中，所有计算首先发生，递归调用是最后发生的事情 .

  取自this超级棒的帖子 . 请考虑阅读 .

  回复于 2024-05-03T06:12:08+08:00
• 119

  在 traditional recursion 中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果 . 以这种方式，在每次递归调用返回之前，您不会得到计算结果 .

  在 tail recursion 中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤 . 这导致最后一个语句采用 (return (recursive-function params)) 的形式 . Basically, the return value of any given recursive step is the same as the return value of the next recursive call .

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

  回复于 2024-05-03T06:12:08+08:00
• 56

  这是前面提到的 tailrecsum 函数的Perl 5版本 .

  sub tail_rec_sum($;$){
    my( $x,$running_total ) = (@_,0);
  
    return $running_total unless $x;
  
    @_ = ($x-1,$running_total+$x);
    goto &tail_rec_sum; # throw away current stack frame
  }
  

  回复于 2024-05-03T06:12:08+08:00
• 24

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

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

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

  注意，对factorial的初始调用必须是阶乘（n，1），其中n是要计算阶乘的数字 .

  回复于 2024-05-03T06:12:08+08:00
• 7

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

  我在这个主题上写了一篇blog帖子，里面有堆栈帧的图形示例 .

  回复于 2024-05-03T06:12:08+08:00
• 1385

  尾递归是一种递归函数，其中函数在函数的末尾（“尾部”）调用自身，其中在递归调用返回之后不进行任何计算 . 许多编译器优化将递归调用更改为尾递归或迭代调用 .

  考虑计算数字因子的问题 .

  一个简单的方法是：

  factorial(n):
  
      if n==0 then 1
  
      else n*factorial(n-1)
  

  假设你调用factorial（4） . 递归树将是：

  factorial(4)
         /        \
        4      factorial(3)
       /             \
      3          factorial(2)
     /                  \
    2                factorial(1)
   /                       \
  1                       factorial(0)
                              \
                               1
  

  上述情况下的最大递归深度为O（n） .

  但是，请考虑以下示例：

  factAux(m,n):
  if n==0  then m;
  else     factAux(m*n,n-1);
  
  factTail(n):
     return factAux(1,n);
  

  factTail（4）的递归树将是：

  factTail(4)
     |
  factAux(1,4)
     |
  factAux(4,3)
     |
  factAux(12,2)
     |
  factAux(24,1)
     |
  factAux(24,0)
     |
    24
  

  这里，最大递归深度是O（n），但没有一个调用将任何额外的变量添加到堆栈 . 因此编译器可以取消堆栈 .

  回复于 2024-05-03T06:12:08+08:00
• 3

  这是一个例子，而不是用文字解释 . 这是阶乘函数的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尾递归函数使用常量堆栈空间 .

  回复于 2024-05-03T06:12:08+08:00