我写了这段代码,我假设len是尾递归,但仍然会发生堆栈溢出.怎么了？
myLength :: [a] -> Integer
myLength xs = len xs 0
where len [] l = l
len (x:xs) l = len xs (l+1)
main = print $ myLength [1..10000000]
尾递归是函数式语言中一个重要的性能优化策略,因为它允许递归调用消耗常量堆栈(而不是O(n)).
是否有任何问题根本无法以尾递归方式编写,或者总是可以将天真递归函数转换为尾递归函数？
如果是这样,有一天功能编译器和解释器可能足够智能以自动执行转换？
除非方法是最终的,否则为什么Scala编译器不会应用尾调用优化？
例如,这个:
class C {
@tailrec def fact(n: Int, result: Int): Int =
if(n == 0)
result
else
fact(n - 1, n * result)
}
结果是
错误:无法优化@tailrec带注释的方法:它既不是私有的也不是最终的,因此可以被覆盖
如果编译器在这种情况下应用TCO,究竟会出现什么问题呢？
我对Scala的新手在尝试阅读David Pollack的Beggining Scala时有点新意.他定义了一个简单的递归函数,它从文件中加载所有字符串:
def allStrings(expr: => String): List[String] = expr match {
case null => Nil
case w => w :: allStrings(expr)
}
它优雅而且很棒,只是当我试图加载一个庞大的字典文件时它抛出了一个StackOverflow异常.
现在据我所知,Scala支持尾递归,因此函数调用不可能溢出堆栈,可能编译器无法识别它？所以经过一些谷歌搜索后我尝试了@tailrec注释来帮助编译器,但它说
error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
def allStrings(expr: => String): List[String] =
我理解尾递归错了吗？我该如何修复此代码？
出于好奇,我试图使用C#生成尾调用操作码.Fibinacci是一个简单的,所以我的c#示例如下所示:
private static void Main(string[] args)
{
Console.WriteLine(Fib(int.MaxValue, 0));
}
public static int Fib(int i, int acc)
{
if (i == 0)
{
return acc;
}
return Fib(i - 1, acc + i);
}
如果我在发布中构建并在没有调试的情况下运行它,我就不会出现堆栈溢出.在没有优化的情况下调试或运行它,我确实得到了堆栈溢出,这意味着尾部调用在发布时具有优化功能(这是我的预期).
这个MSIL看起来像这样:
.method public hidebysig static int32 Fib(int32 i, int32 acc) cil managed
{
// Method Start RVA 0x205e
// Code Size 17 (0x11)
.maxstack 8
L_0000: ldarg.0
L_0001: brtrue.s L_0005
L_0003: ldarg.1
L_0004: ret
L_0005: ldarg.0
L_0006: ldc.i4.1
L_0007: sub
L_0008: ldarg.1
L_0009: ldarg.0
L_000a: …这里有两个解决方案,在Cay Horstmann的Scala for the Impatient中运用4.9:"写一个函数lteqgt(values:Array [Int],v:Int),它返回一个包含小于v的值的三元组,等于v,并且大于v." 一个使用尾递归,另一个使用while循环.我认为两者都会编译成类似的字节码,但是while循环比尾递归慢了近两倍.这告诉我,我的while方法编写得很糟糕.
import scala.annotation.tailrec
import scala.util.Random
object PerformanceTest {
def main(args: Array[String]): Unit = {
val bigArray:Array[Int] = fillArray(new Array[Int](100000000))
println(time(lteqgt(bigArray, 25)))
println(time(lteqgt2(bigArray, 25)))
}
def time[T](block : => T):T = {
val start = System.nanoTime : Double
val result = block
val end = System.nanoTime : Double
println("Time = " + (end - start) / 1000000.0 + " millis")
result
}
@tailrec def fillArray(a:Array[Int], pos:Int=0):Array[Int] = {
if (pos == a.length)
a
else { …我是F#的新手,正在阅读有关尾递归函数的内容,希望有人可以给我两个不同的函数foo实现 - 一个是尾递归的,另一个不是我可以更好地理解这个原理.
我经常听到人们说C不执行尾部呼叫消除.虽然标准不能保证,但是无论如何,它是否在实践中通过任何体面的实现来执行？假设你只针对成熟的,实现良好的编译器而不关心为模糊平台编写的原始编译器的绝对最大可移植性,那么在C中依赖尾调用是否合理呢？
另外,将尾部呼叫优化留在标准之外的理由是什么？
到目前为止,Go编程语言是否优化尾调用？如果没有,它是否至少优化了函数的尾递归调用？