标签: tail-recursion

我有两个代码片段,试图将浮动列表转换为Vector3或Vector2列表.这个想法是从列表中一次取2/3个元素并将它们组合成一个向量.最终结果是一系列向量.

    let rec vec3Seq floatList =
        seq {
            match floatList with
            | x::y::z::tail -> yield Vector3(x,y,z)
                               yield! vec3Seq tail
            | [] -> ()
            | _ -> failwith "float array not multiple of 3?"
            }

    let rec vec2Seq floatList =
        seq {
            match floatList with
            | x::y::tail -> yield Vector2(x,y)
                            yield! vec2Seq tail
            | [] -> ()
            | _ -> failwith "float array not multiple of 2?"
            }

代码看起来很相似,但似乎无法提取公共部分.有任何想法吗？

这是我在Clojure中实现的Erathosthene筛选(基于关于流的SICP课程):

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

现在,当我拿到前100个素数时,一切都好了:

(take 100 primes)

但是,如果我尝试采用前1000个素数,因为堆栈溢出而导致程序中断.我想知道是否有可能改变某种功能筛选成尾递归,并且仍然保留算法的"流"？

任何帮助???

通过搜索此站点和Web上的其他位置,JVM不支持尾调用优化.因此,这是否意味着如果要在JVM上运行,则不应写入可能在非常大的输入列表上运行的尾递归Scala代码(如下所示)？

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

Martin Odersky的Scala示例包含以下段落,似乎表明存在适合递归的情况或其他环境:

原则上,尾调用总是可以重用调用函数的堆栈帧.但是,某些运行时环境(例如Java VM)缺少基本条件,以使堆栈帧重用用于尾调用.因此,生产质量Scala实现只需要重新使用直接尾递归函数的堆栈帧,其最后一个操作是对自身的调用.其他尾调用也可以进行优化,但不应该在实现中依赖于此.

任何人都能解释一下这段中间两句话是什么意思吗？

谢谢!

我正在学习F#(一般来说是功能编程的新手,虽然多年来使用C#的功能方面,但让我们面对它,这是非常不同的)我读过的一件事是F#编译器识别尾递归并编译它进入一个while循环(参见http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).

我不明白的是,为什么你会写一个递归函数而不是一个while循环,如果那就是它将会变成什么.特别是考虑到你需要做一些额外的工作来使你的函数递归.

我有一种感觉,有人可能会说while循环不是特别功能,你想要所有功能和诸如此类的东西,所以你使用递归,但那么为什么编译器将它变成while循环就足够了？

谁可以给我解释一下这个？

当我写这个函数时,我知道我不会得到尾调优化.我仍然没有想出一个处理这个的好方法,并希望别人可以提供建议.

我有一棵树:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

我想要计算其中有多少个节点:

let count h =
    let rec count' h acc =
        match h with 
        | E -> 0 + acc
        | T(_, value, leftChild, rightChild) ->
            let acc = 1 + acc
            (count' leftChild acc) + (count' rightChild acc)

    count' h 0

由于添加了子节点的计数,因此未进行优化.如果树有100万个节点,任何想法如何制作这样的东西？

谢谢,德里克

这是使用CPS实现计数.它仍然吹响了堆栈.

let count h =
    let rec count' h acc cont =
        match h with
        | E -> cont …

我一直在努力理解continuation/CPS,并且从我可以收集的内容中建立一个延迟计算,一旦我们到达列表的末尾,我们就会调用最终的计算.

我不明白的是,为什么CPS会阻止堆栈溢出,因为它看起来类似于按照示例1中的天真方法构建嵌套函数.对于长篇文章感到抱歉但是试图表明这个想法(可能在哪里出错)基本:

所以:

let list1 = [1;2;3]

例1:"天真的方法"

let rec sumList = function
    |[] -> 0
    |h::t -> h + sumList t

因此,当它运行时,迭代地导致:

1. 1 + sumList [2;3]
2. 1 + (2 + sumList [3])
3. 1 + (2 + (3 + 0))

因此,Tail Recursion可以克服嵌套(和溢出问题) - 运行累加器即

"示例2:尾递归"

let sumListACC lst =
    let rec loop l acc =
        match l with
        |[] -> acc
        |h::t -> loop t (h + acc)
    loop lst 0

即

1. sumList[2;3] (1+0)
2. sumList[3] (2+1)
3. sumList[] (3+3)

因此,因为在每一步都评估累加器,所以没有嵌套,我们避免破坏堆栈.明确!

接下来是CPS,我知道当我们已经有一个累加器时这是必需的但是函数不是尾递归的,例如使用Foldback.虽然在上面的示例中不需要,但将CPS应用于此问题会给出: …

我很困惑为什么这个功能显示内存不断增加

let rec startRead1() = 
  async {
    do! Async.Sleep 1
    System.GC.Collect()
    let mem = System.GC.GetTotalMemory(true)
    printfn "%d" mem
    do! startRead1()
  }

25676 36760 36840 36884 36928 36972 37016 37060 37104 37328 37362 37212 37456 37500 37544 37588 37632 37676 37720 37764 37808 37852 37896 37940 37984 38028 38072 38116 38160 38204 38248 38292 38336 38380 38424 38468 38512 38556 38600 38644 38688 38732 38776 38820 38864 38908 38952 38996 39040 39084 39128 39172 39216 ^ C按任意键继续...

[<EntryPoint>]
let main _ …

只是想直截了当.考虑这个Erlang代码的例子:

 test() ->
      receive
          {From, whatever} ->
                %% do something
               test();
          {From, somethingelse} ->
               %% do something else
               test();
 end.

是不是test()调用,只是一个转到？

我问这个是因为在C中我们了解到,如果你进行函数调用,返回位置总是放在堆栈上.我无法想象这里的Erlang一定是这种情况,因为这会导致堆栈溢出.

基本的.我们有两种不同的调用函数的方法:goto和gosub.goto刚刚把程序流引导到其他地方,gosub记得你来自哪里,所以你可以回来.

考虑到这种思维方式,我可以更容易地看一下erlang的递归,因为如果我只读:test()作为goto,那么根本就没有问题.

因此我的问题:不是erlang只是使用goto而不是记住堆栈上的返回地址？

编辑:

只是为了澄清我的观点:

我知道goto可以用在某些语言中来跳过这个地方.但是,只是suupose而不是someFunction()你也可以这样做:在第一个例子中返回流返回的一些函数(),在第二个例子中,流程只在someFunction中继续并且永远不会返回.

所以我们通过跳转到方法起点来限制正常的GOTO行为.

如果你这样看,那么erlang递归函数调用看起来就像一个goto.

(在我看来,goto是一个函数调用,无法返回你来自的地方).这正是erlang示例中正在发生的事情.

我正在使用F#规范的最终工作流程的修改版本,以便在Xbox上进行开发.看来,Xbox上的.net框架不支持尾调用.因此,我必须在编译时禁用尾调用优化.

虽然最初似乎这种限制会阻止在计算表达式中使用任何形式的循环,但我最初认为"步进"可以避免这个问题:计算表达式中的递归函数f不直接调用自身,而是返回一个包含lambda的最终值,该lambda调用f.

实验表明我对while循环是正确的(它们在计算表达式中使用时不会导致堆栈溢出),但不是关于递归函数.

为了澄清,这有效:

// Wait until "start" or "A" is pressed on one of the gamepads.
// Set "player" when that happens.
let player : PlayerIndex option ref = ref None
while (!player).IsNone do
    for p in all_players do
        let state = GamePad.GetState(p)
        if state.IsConnected
            && (state.Buttons.Start = ButtonState.Pressed
                || state.Buttons.A = ButtonState.Pressed) then
            player := Some p
    do! sys.WaitNextFrame()

这会导致堆栈溢出:

// Wait until "start" is pressed on the controlling gamepad.
let rec wait() = task {
    input.Update()
    if …

我编写了一个天真的测试平台来测量三种阶乘实现的性能:基于循环,非尾递归和尾递归.

令我惊讶的是,最差的性能是循环的(«while»预计效率更高,所以我提供了两者) ,其成本几乎是尾部递归替代的两倍.

答案:修复循环实现,避免使用BigInt的*=运算符,因为其内部«循环»变得如预期的那样快

我遇到的另一个"woodoo"行为是StackOverflow异常,在非尾递归实现的情况下,对于相同的输入没有抛出异常.我可以通过逐步调用具有越来越大的值的函数来规避StackOverlow ...我感到很疯狂:) 答案:JVM需要在启动期间收敛,然后行为是连贯的和系统的

这是代码:

final object Factorial {
  type Out = BigInt

  def calculateByRecursion(n: Int): Out = {
    require(n>0, "n must be positive")

    n match {
      case _ if n == 1 => return 1
      case _ => return n * calculateByRecursion(n-1)
    }
  }

  def calculateByForLoop(n: Int): Out = {
    require(n>0, "n must be positive")

    var accumulator: Out = 1
    for (i <- 1 to n)
      accumulator = i * accumulator
    accumulator
  }

  def calculateByWhileLoop(n: …