标签: tail-call-optimization

我刚刚进行了一次讨论，讨论了以下两段 C 代码：

For 循环：

#include <stdio.h>
#define n (196607)

int main() {
  long loop;
  int count=0;
  for (loop=0;loop<n;loop++) {
    count++;
  }
  printf("Result = %d\n",count);

  return 0;
}

递归：

#include <stdio.h>
#define n (196607)

long recursive(long loop) {
  return (loop>0) ? recursive(loop-1)+1: 0;
}

int main() {
  long result;
  result = recursive(n);
  printf("Result = %d\n",result);
  return 0;
}

看到这段代码时，我看到并想到“啊，这不是尾部调用递归”，因为它在调用完成recursive(loop-1)+1后还有工作要做；recursive它需要增加返回值。

果然，在没有优化的情况下，递归代码会触发堆栈溢出，正如您所期望的那样。

然而，使用该-O2标志，不会遇到堆栈溢出，我认为这意味着堆栈被重用，而不是将越来越多的内容推入堆栈 - 这就是 tco。

GCC 显然可以检测到这个简单的情况（+1 返回值）并对其进行优化，但是它能走多远？

当递归调用不是最后执行的操作时，gcc 可以使用 tco 优化的限制是什么？

附录：我已经编写了return function(); …

人们说除了没有尾调用优化的限制之外,clojure实现是优秀的 - 限制jvm而不是clojure实现.

http://lambda-the-ultimate.org/node/2547

有人说,将Python实现TCO会牺牲

• 堆栈跟踪转储和
• 调试规律性.

向我解释尾调用优化的重要性以及Python需要它的原因

是否必须为实施TCO的jvm做出同样的牺牲？还有什么需要牺牲的吗？

根据该问题的答案: 如果有的话,哪些C++编译器会进行尾递归优化？ 看起来,编译器应该进行尾递归优化.

但我已经尝试过提出的选项,似乎编译器在模板函数的情况下不能进行这种优化.它能以某种方式修复吗？

我有一个深度递归函数,理论上即使在大输入的情况下也能很好地工作.问题是在撰写本文时我忘记了C#没有很好地进行尾调用优化,如果有的话,所以我得到StackOverflowException了任何复杂足够的输入.该方法的基本结构是两个大方法,每个方法调用另一个.

public object Simplify(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return Simplify(ProcessExpansion(param));
}

二者IsSimple并ProcessExpansion具有相对固定的堆栈深度-唯一的问题是简化和展开之间的递归.你会如何减少堆栈深度？

我正在考虑返回会计算结果的代表,但这看起来有点矫枉过正 - 必须有一种更简单的方法.这是我对解决方案的想法(它不是很精致,因为我一直认为我必须在这里做一些可怕的错误):

public object Simplify(object param) {
    object result = () => SimplifyInternal(param);
    while (result is Func<object>)
        result = ((Func<object>)result)();
    return result;
}

private object SimplifyInternal(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return () => SimplifyInternal(ProcessExpansion(param));
}

所以我的两个问题是:

1. 这个解决方案有什么不可思议的错误？
2. 你能想到一个更好的吗？

我的试探性答案是否定的,如以下测试代码所示:

#include <functional>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void TestFunc (void);
int TestFuncHelper (vector<int>&, int, int);

int main (int argc, char* argv[]) {
    TestFunc ();
    return 0;
} // End main ()

void TestFunc (void) {
    // Recursive lambda
    function<int (vector<int>&, int, int)> r = [&] (vector<int>& v_, int d_, int a_) {
        if (d_ == v_.size ()) return a_;
        else return r (v_, d_ + 1, a_ + v_.at (d_));
    };
    int UpperLimit = 100000; …

在(Common)Lisp中是否可以跳转到另一个函数而不是调用另一个函数？我的意思是,当前函数被打破而另一个被调用,没有跳过数千个函数,就好像我决定自己是否完成尾调用优化,即使它不是尾部.我不确定"(从fn x返回)"是否,我想要什么.

例:

(defun fn (x)
  (when x
    (princ x)
    (jump 'fn (cdr x)))
  (rest))

'jump'应该像调用下面的函数而不保存这个函数的位置,而是返回原来的funcall所在的位置,这样就不会有堆栈溢出.只有x为零才能执行'rest'.

我已经编写了一个函数来递归地求和值,但它不符合ES6尾部调用优化的标准(原因我无法清晰表达).

function sum(...values) {
  if(!values.length) { 
    return 0; 
  }
  return values.shift() + sum(...values);
}

如何更改它才有资格进行优化？

我在Clojure文档中找不到答案。我是Clojure的新手，似乎您可以recur两种不同的方式使用并且基本上得到相同的结果。

范例1：

(defn my-function [num]
  (if (> num 10)
    num
    (recur (+ num 1))))

范例2：

(defn my-function [num]
  (loop [cnt num]
    (if (> cnt 10)
      cnt
      (recur (+ cnt 1)))))

据我所知，这两种形式似乎做的完全相同。我知道，recur总体上讲，这样做的原因是好的，因为在适当的情况下，编译器可以破解某种伪尾部调用优化方法，我非常喜欢并且希望尽可能多地利用它。所以这是我的问题：

1. loop如果recur没有它，似乎什么也可以使用？
2. 是否loop仅创建“递归范围”，就像let创建迷你范围一样？
3. 如果是这样，我仍然可以不使用而获得尾递归收益loop吗？

问题Stack尽管尾部调用位置溢出但仅在64位导致发现F#编译器中的错误.

在阅读答案后,我很好奇导致找到错误的原因,因为我希望更好地提高我解决问题和理解TCO的技能.

我有这个函数,在列表中找到偶数,并返回一个只包含这些数字的新列表:

  def even([]), do: []

  def even([head | tail]) when rem(head, 2) == 0 do
    [head | even(tail)]
  end

  def even([_head| tail]) do
    even(tail)
  end

这是否已经优化了尾调用？或者每个子句都必须在最后调用自己("偶数"函数的第二个版本不是)？如果没有,如何重构为尾调用递归？

我知道这可以通过过滤器或减少来完成,但我想尝试没有它.