我经常听到人们说C不执行尾部呼叫消除.虽然标准不能保证,但是无论如何,它是否在实践中通过任何体面的实现来执行？假设你只针对成熟的,实现良好的编译器而不关心为模糊平台编写的原始编译器的绝对最大可移植性,那么在C中依赖尾调用是否合理呢？
另外,将尾部呼叫优化留在标准之外的理由是什么？
到目前为止,Go编程语言是否优化尾调用？如果没有,它是否至少优化了函数的尾递归调用？
有可能以某种方式结合memoization和tail-recursion吗？我现在正在学习F#并理解这两个概念,但似乎无法将它们结合起来.
假设我有以下memoize功能(来自Real-World Functional Programming):
let memoize f = let cache = new Dictionary<_, _>()
(fun x -> match cache.TryGetValue(x) with
| true, y -> y
| _ -> let v = f(x)
cache.Add(x, v)
v)
以及以下factorial功能:
let rec factorial(x) = if (x = 0) then 1 else x * factorial(x - 1)
记忆factorial并不太难,并且使尾递归也不是:
let rec memoizedFactorial =
memoize (fun x -> if (x = 0) then 1 else x * memoizedFactorial(x - …我编写了一小段代码,如果尾递归被优化,我认为应该成功,但它会炸毁堆栈.我是否应该总结PHP不优化尾递归？
function sumrand($n,$sum) {
if ($n== 0) {
return $sum;
}
else {
return (sumrand($n-1,$sum+rand(0,1)));
}
}
echo sumrand(500000,0)."\n";
我有这个"学习代码",我为f#中的morris seq编写,它遇到堆栈溢出,我不知道如何避免."morris"返回无限序列的"看见和说出"序列(即{{1},{1,1},{2,1},{1,2,1,1},{1,1,1 ,2,2,1},{3,1,2,2,1,1},...}).
let printList l =
Seq.iter (fun n -> printf "%i" n) l
printfn ""
let rec morris s =
let next str = seq {
let cnt = ref 1 // Stack overflow is below when enumerating
for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
if cur.[0] <> cur.[1] then
yield!( [!cnt ; cur.[0]] )
cnt := 0
incr cnt
}
seq {
yield s
yield! morris (next s) // tail recursion, no stack …在制定另一个SO问题的答案时,我在Mathematica中遇到了一些关于尾递归的奇怪行为.
在数学文档暗示,尾调用优化的可能被执行.但我自己的实验给出了相互矛盾的结果.对比,例如,以下两个表达式.第一个崩溃7.0.1内核,可能是由于堆栈耗尽:
(* warning: crashes the kernel! *)
Module[{f, n = 0},
f[x_] := (n += 1; f[x + 1]);
TimeConstrained[Block[{$RecursionLimit = Infinity}, f[0]], 300, n]
]
第二个运行完成,似乎利用尾调用优化来返回有意义的结果:
Module[{f, n = 0},
f[x_] := Null /; (n += 1; False);
f[x_] := f[x + 1];
TimeConstrained[Block[{$IterationLimit = Infinity}, f[0]], 300, n]
]
两个表达式都定义了尾递归函数f.在第一个函数的情况下,Mathematica显然认为复合语句的存在足以击败尾调用优化的任何机会.还要注意,第一个表达式由$RecursionLimit第二个表达式控制,第二个表达式由$IterationLimitMathematica以不同方式处理这两个表达式.(注意:上面提到的SO答案有一个较少设法的功能,成功利用尾部调用优化).
所以,问题是:有没有人知道Mathematica对递归函数进行尾调用优化的情况？在Mathematica文档或其他WRI材料中提及最终陈述将是理想的.投机也很受欢迎.
recursion wolfram-mathematica tail-recursion tail-call-optimization
在Haskell Wiki的monad中的递归中有一个声称是尾递归的例子:
f 0 acc = return (reverse acc)
f n acc = do
v <- getLine
f (n-1) (v : acc)
虽然命令式符号使我们相信它是尾递归的,但它根本不是那么明显(至少对我而言).如果我们去糖,do我们得到
f 0 acc = return (reverse acc)
f n acc = getLine >>= \v -> f (n-1) (v : acc)
并重写第二行导致
f n acc = (>>=) getLine (\v -> f (n-1) (v : acc))
所以我们看到它f发生在第二个参数内>>=,而不是在尾递归位置.我们需要考察IO的>>=得到答案.显然,将递归调用作为do块中的最后一行是一个尾递归函数的充分条件.
假设monad是尾递归的,如果这个monad中的每个递归函数都定义为 …
我不能想到在规范中也有尾调用优化的真正的RAII语言,但我知道许多C++实现可以作为特定于实现的优化来实现.
这给那些那些实现了一个问题:因为析构函数,并在自动变量的作用域结束时被调用不是由一个单独的垃圾收集例程,是不是违反TCO的约束,递归调用必须在最后的指令功能结束？
例如:-
#include <iostream>
class test_object {
public:
test_object() { std::cout << "Constructing...\n"; }
~test_object() { std::cout << "Destructing...\n"; }
};
void test_function(int count);
int main()
{
test_function(999);
}
void test_function(int count)
{
if (!count) return;
test_object obj;
test_function(count - 1);
}
"构建......"将写入999次,然后"破坏......"再写999次.最终,test_object在展开之前将自动分配999个实例.但假设一个实现有TCO,那么1000个堆栈帧是存在还是仅存在1？
递归调用之后的析构函数是否与事实上的TCO实现要求相冲突？
一位朋友在Clojure中给了我这段代码片段
(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))
并问我如何对付类似的Scala实现.
我写的Scala代码看起来像这样:
def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))
val ints = from(1).take(9999998)
def add(a: Stream[Int], b: Long): Long = {
if (a.isEmpty) b else add(a.tail, b + a.head)
}
val t1 = System.currentTimeMillis()
println(add(ints, 0))
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float] + " msecs")
底线是:Clojure中的代码在我的机器上运行大约1.8秒并且使用少于5MB的堆,Scala中的代码运行大约12秒并且512MB的堆是不够的(如果我设置了它,它完成计算堆到1GB).
所以我想知道为什么在这种特殊情况下Clojure会更快更轻薄？你有一个Scala实现在速度和内存使用方面有类似的行为吗？
请不要发表宗教言论,我的兴趣在于找出主要是什么使得clojure在这种情况下如此快速,并且如果在scala中更快地实现算法.谢谢.
performance scala tail-recursion clojure tail-call-optimization
显然,对于Python是否需要尾调用优化,存在很大的争议.当有人向Guido发送SICP副本时,这个问题就出现了,因为他没有"得到它".我和Guido在同一条船上.我理解尾调用优化的概念.我真的想不出Python真正需要它的任何理由.
为了让我更容易理解,有人可以给我一些代码片段,使用TCO可以大大简化吗？