标签: tail-recursion

我有一个尾递归寻路算法,我已经在Javascript中实现,并想知道是否有任何(所有？)浏览器可能会得到堆栈溢出异常.

我今天在unix中发现了"time"命令,并认为我会用它来检查Haskell中尾递归和正常递归函数之间运行时的差异.

我写了以下函数:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

这些都是有效的,记住它们只是用于这个项目,所以我没有费心去检查零或负数.

但是,在为每个编写一个main方法,编译它们,并使用"time"命令运行它们时,两者都具有相似的运行时,正常的递归函数使尾递归函数边缘化.这与我在lisp中关于尾递归优化的内容相反.这是什么原因？

我试图弄清楚C#编译器如何处理尾调用.

(答案:他们不是.但是64位JIT会做TCE(尾部呼叫消除).限制适用.)

所以我使用递归调用编写了一个小测试,它打印了在StackOverflowException杀死进程之前调用它的次数.

class Program
{
    static void Main(string[] args)
    {
        Rec();
    }

    static int sz = 0;
    static Random r = new Random();
    static void Rec()
    {
        sz++;

        //uncomment for faster, more imprecise runs
        //if (sz % 100 == 0)
        {
            //some code to keep this method from being inlined
            var zz = r.Next();  
            Console.Write("{0} Random: {1}\r", sz, zz);
        }

        //uncommenting this stops TCE from happening
        //else
        //{
        //    Console.Write("{0}\r", sz); …

我想测试foldl vs foldr.从我所看到的,你应该使用foldl over foldr,因为尾部递归优化.

这是有道理的.但是,运行此测试后,我很困惑:

foldr(使用时间命令时需要0.057秒):

a::a -> [a] -> [a]
a x = ([x] ++ )

main = putStrLn(show ( sum (foldr a [] [0.. 100000])))

foldl(使用time命令时需要0.089s):

b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])

main = putStrLn(show ( sum (foldl b [] [0.. 100000])))

很明显,这个例子很简单,但我很困惑为什么foldr击败foldl.这不应该是foldl获胜的明显案例吗？

Scala是否支持尾递归优化？

我将介绍函数式编程[FP](使用Scala).从我最初的学习中得出的一点是,FP很大程度上依赖于递归.而且似乎在纯 FP中,执行迭代的唯一方法是编写递归函数.

由于递归的大量使用似乎FPs不得不担心的下一件事StackoverflowExceptions通常是由于长缠绕递归调用.通过引入一些优化(@tailrec从Scala v2.8开始维护堆栈帧和注释中的尾递归相关优化)来解决这个问题

有人可以请教我为什么递归对函数式编程范式如此重要？如果我们迭代地执行某些操作,那么函数式编程语言的规范中是否会出现"违反"的内容？如果是,那么我也很想知道这一点.

PS:请注意,我是函数式编程的新手,所以如果他们解释/回答我的问题,请随时向我指出现有资源.另外我也明白Scala特别为迭代的东西提供支持.

我最近在Python程序员面前发现了一个关于F#的演示文稿,看了之后,我决定自己实现"蚂蚁拼图"的解决方案.

有一只蚂蚁可以在平面网格上走动.蚂蚁可以一次向左,向右,向上或向下移动一个空间.也就是说,从单元格(x,y),蚂蚁可以进入单元格(x + 1,y),(x-1,y),(x,y + 1)和(x,y-1).蚂蚁无法访问x和y坐标的数字之和大于25的点.例如,点(59,79)是不可访问的,因为5 + 9 + 7 + 9 = 30,大于25.问题是:如果从(1000,1000)开始,蚂蚁可以访问多少个点,包括(1000,1000)本身？

我首先在30行OCaml中实现了我的解决方案,并尝试了它:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

整洁,我的结果与leonardo在D和C++中的实现相同.与leonardo的C++实现相比,OCaml版本的运行速度比C++慢大约2倍.这是好的,因为leonardo使用队列来删除递归.

然后我将代码翻译成F# ......这就是我得到的:

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit …

如何判断gcc(更具体地说,g ++)是否在特定函数中优化尾递归？(因为它出现了几次:我不想测试gcc是否可以优化尾递归.我想知道它是否优化了我的尾递归函数.)

如果您的答案是"查看生成的汇编程序",我想知道我正在寻找什么,以及我是否可以编写一个简单的程序来检查汇编程序以查看是否存在优化.

PS.我知道这似乎是问题的一部分,如果有的话,C++编译器会进行尾递归优化吗？从5个月前.但是,我不认为这个问题的这一部分得到了令人满意的答复.(答案是"检查编译器是否进行了优化(我知道)的最简单方法是执行调用,否则会导致堆栈溢出 - 或者查看汇编输出.")

有人可以在C++中向我展示一个简单的尾递归函数吗？

为什么尾部递归更好,如果它甚至是？

除了尾递归之外还有哪些其他类型的递归？

我一直试图Tail call optimization在JavaScript的上下文中理解并编写了下面的递归和尾递归方法factorial().

递归:

function factorial (n) {
  if (n < 2) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

尾递归:

function factorial (n) {
  function fact(n, acc) {
    if (n < 2) {
      return acc;
    } else {
      return fact(n-1, n * acc);
    }
  }

  return fact(n, 1)
}

但我不确定tail-recursive该函数的版本是否会被JavaScript编译器优化,因为它是在Scala等其他语言中完成的.有人可以帮我解决这个问题吗？