什么是尾部呼叫优化？

8 回答

• 2

  尾调用优化是您可以避免为函数分配新堆栈帧的地方，因为调用函数将只返回它从被调用函数获得的值 . 最常见的用法是尾递归，其中为利用尾调用优化而编写的递归函数可以使用常量堆栈空间 .

  Scheme是规范中保证任何实现都必须提供此优化的少数编程语言之一（JavaScript也从ES6开始），因此这里有两个Scheme中的阶乘函数示例：

  (define (fact x)
    (if (= x 0) 1
        (* x (fact (- x 1)))))
  
  (define (fact x)
    (define (fact-tail x accum)
      (if (= x 0) accum
          (fact-tail (- x 1) (* x accum))))
    (fact-tail x 1))
  

  第一个函数不是尾递归，因为在进行递归调用时，函数需要跟踪调用返回后它需要对结果进行的乘法运算 . 因此，堆栈如下所示：

  (fact 3)
  (* 3 (fact 2))
  (* 3 (* 2 (fact 1)))
  (* 3 (* 2 (* 1 (fact 0))))
  (* 3 (* 2 (* 1 1)))
  (* 3 (* 2 1))
  (* 3 2)
  6
  

  相反，尾递归阶乘的堆栈跟踪如下所示：

  (fact 3)
  (fact-tail 3 1)
  (fact-tail 2 3)
  (fact-tail 1 6)
  (fact-tail 0 6)
  6
  

  正如您所看到的，我们只需要跟踪每次调用事实尾部的相同数据量，因为我们只是将我们直接返回的值返回到顶部 . 这意味着即使我打电话（事实1000000），我只需要与（事实3）相同的空间 . 非尾递归事实不是这种情况，因此大的值可能导致堆栈溢出 .

  回复于 2024-05-06T20:13:14+08:00
• 155

  让我们来看一个简单的例子：在C中实现的阶乘函数 .

  我们从明显的递归定义开始

  unsigned fac(unsigned n)
  {
      if (n < 2) return 1;
      return n * fac(n - 1);
  }
  

  如果函数返回之前的最后一个操作是另一个函数调用，则函数以尾调用结束 . 如果此调用调用相同的函数，则它是尾递归的 .

  即使 fac() 乍一看看起来是尾递归的，但事实并非如此

  unsigned fac(unsigned n)
  {
      if (n < 2) return 1;
      unsigned acc = fac(n - 1);
      return n * acc;
  }
  

  即最后一个操作是乘法，而不是函数调用 .

  但是，通过将累积值作为附加参数传递给调用链并仅将最终结果作为返回值再次传递，可以将 fac() 重写为尾递归：

  unsigned fac(unsigned n)
  {
      return fac_tailrec(1, n);
  }
  
  unsigned fac_tailrec(unsigned acc, unsigned n)
  {
      if (n < 2) return acc;
      return fac_tailrec(n * acc, n - 1);
  }
  

  现在，为什么这有用？因为我们在尾调用之后立即返回，所以我们可以在尾部位置调用函数之前丢弃先前的堆栈帧，或者，在递归函数的情况下，按原样重用堆栈帧 .

  尾调用优化将我们的递归代码转换为

  unsigned fac_tailrec(unsigned acc, unsigned n)
  {
  TOP:
      if (n < 2) return acc;
      acc = n * acc;
      n = n - 1;
      goto TOP;
  }
  

  这可以内联到 fac() ，我们到达

  unsigned fac(unsigned n)
  {
      unsigned acc = 1;
  
  TOP:
      if (n < 2) return acc;
      acc = n * acc;
      n = n - 1;
      goto TOP;
  }
  

  这相当于

  unsigned fac(unsigned n)
  {
      unsigned acc = 1;
  
      for (; n > 1; --n)
          acc *= n;
  
      return acc;
  }
  

  正如我们在这里看到的，一个足够先进的优化器可以用迭代替换尾递归，这样可以避免函数调用开销并且仅使用恒定量的堆栈空间 .

  回复于 2024-05-06T20:13:14+08:00
• 470

  TCO（尾调用优化）是智能编译器可以调用函数并且不占用额外堆栈空间的过程 . 发生这种情况的唯一情况是，如果函数 f 中执行的最后一条指令是对函数g的调用（注意： g 可以是 f ） . 这里的关键是 f 不再需要堆栈空间 - 它只是调用 g 然后返回 g 将返回的任何内容 . 在这种情况下，可以进行优化，g只运行并返回它对调用f的东西所具有的任何值 .

  这种优化可以使递归调用占用不变的堆栈空间，而不是爆炸 .

  示例：此阶乘函数不是TCOptimizable：

  def fact(n):
      if n == 0:
          return 1
      return n * fact(n-1)
  

  除了在return语句中调用另一个函数之外，该函数还可以执

  以下功能是TCOptimizable：

  def fact_h(n, acc):
      if n == 0:
          return acc
      return fact_h(n-1, acc*n)
  
  def fact(n):
      return fact_h(n, 1)
  

  这是因为在这些函数中发生的最后一件事是调用另一个函数 .

  回复于 2024-05-06T20:13:14+08:00
• 592

  我发现尾部调用，递归尾调用和尾调用优化的最佳高级描述可能是博客文章

  "What the heck is: A tail call"

  作者Dan Sugalski . 关于尾调用优化，他写道：

  暂时考虑一下这个简单的函数：sub foo（int a）{
  a = 15;
  返回栏（a）;
  }
  那么，你或者你的语言编译器能做什么呢？那么，它可以做的是转换表单的代码返回somefunc（）;进入低级序列弹出堆栈帧;转到somefunc（）;.在我们的例子中，这意味着在我们调用bar之前，foo清理自己然后，而不是调用bar作为子例程，我们做一个低级goto操作酒吧的开始 . Foo已经从堆栈中清除了自己，所以当bar启动时，看起来无论谁调用foo都真的调用了bar，当bar返回它的值时，它会直接将它返回给调用foo的人，而不是将它返回给foo然后返回它给它的来电者 .

  并在尾递归：

  如果函数作为最后一个操作返回调用自身的结果，则会发生尾递归 . 尾部递归更容易处理，因为你不必在某个地方跳到某个随机函数的开头，而只是回到自己的开头，这是一件很容易做的事情 .

  这样：

  sub foo（int a，int b）{
  if（b == 1）{
  返回;
  } else {
  return foo（a * a a，b - 1）;
  }

  悄然变成：

  sub foo（int a，int b）{
  标签：
  if（b == 1）{
  返回;
  } else {
  a = a * a a;
  b = b - 1;
  转到标签;
  }

  我喜欢这个描述的是那些来自命令式语言背景（C，C，Java）的人如何简洁易懂

  回复于 2024-05-06T20:13:14+08:00
• 6

  首先要注意的是，并非所有语言都支持它 .

  TCO适用于递归的特殊情况 . 它的要点是，如果你在函数中做的最后一件事是调用自身（例如它从“尾部”位置调用自身），编译器可以优化它，就像迭代而不是标准递归一样 .

  您会看到，通常在递归期间，运行时需要跟踪所有递归调用，以便在返回时它可以在上一次调用时恢复，依此类推 . （尝试手动写出递归调用的结果，以便直观地了解其工作原理 . ）跟踪所有调用会占用空间，当函数调用自身时会占用很多空间 . 但是对于TCO，它可以说“回到开头，只是这次将参数值更改为这些新值 . ”它可以做到这一点，因为在递归调用之后没有任何内容引用那些值 .

  回复于 2024-05-06T20:13:14+08:00
• 12

  看这里：

  http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

  您可能知道，递归函数调用可能会对堆栈造成严重破坏;很容易快速耗尽堆栈空间 . 尾调用优化是一种可以创建使用常量堆栈空间的递归样式算法的方法，因此它不会增长和增长，并且会出现堆栈错误 .

  回复于 2024-05-06T20:13:14+08:00
• 4

  • 我们应该确保函数本身没有goto语句 . 函数调用是被调用函数中的最后一件事 .

  • 大规模递归可以将其用于优化，但是在小规模中，使函数调用尾调用的指令开销减少了实际目的 .

  • TCO可能会导致永久运行的功能：

  void eternity()
  {
      eternity();
  }
  

  回复于 2024-05-06T20:13:14+08:00
• 47

  递归函数方法存在问题 . 它构建了一个大小为O（n）的调用堆栈，这使得我们的总内存成本为O（n） . 这使得它容易受到堆栈溢出错误的影响，其中调用堆栈变得太大并且空间不足 . 尾部成本优化（TCO）计划 . 它可以优化递归函数，以避免构建一个高调用堆栈，从而节省内存成本 .

  有许多语言正在进行TCO，如（Javascript，Ruby和少数C），而Python和Java不做TCO .

  JavaScript语言已确认使用:) http://2ality.com/2015/06/tail-call-optimization.html

  回复于 2024-05-06T20:13:14+08:00