标签: tail-recursion

haskell的方法是什么？

for (int i = 0 ; i < 1000 ; i++)
      for (int j = 0 ; j < 1000 ; j++)
              ret =  foo(i , j )           #I need the return value.

更多背景:我正在解决欧拉问题27,我得到了:

 value a  b =
     let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..]
     in (l, a ,b)

下一步是通过循环遍历所有可能的a和b来获取元组列表,然后执行以下处理:

foldl (\(max,v) (n,a,b)-> if n > max then (n , a * b) else (max ,v) ) …

我想知道oCaml是否优化了这个代码是尾递归的,如果是这样的话F#？

let rec sum xs =
  match xs with
    | [] -> 0
    | x :: xs' -> x + sum xs'

在Scala 2.8.x中,添加了一个新的注释(@tailrec),如果编译器无法对带注释的方法执行尾调用优化,则会产生编译时错误.

在Clojure中是否有类似的设施loop/recur？

编辑: 在阅读我的问题的第一个答案(谢谢,Bozhidar Batsov)并进一步搜索Clojure文档后,我发现了这个问题:

(recur exprs*)
按顺序计算exprs,然后并行地将递归点的绑定重新绑定到exprs的值.如果递归点是fn方法,那么它会重新引导params.如果递归点是一个循环,那么它会重新绑定循环绑定.执行然后跳回到递归点.recur表达式必须与递归点的arity完全匹配.特别是,如果递归点是可变参数fn方法的顶部,则不会收集休息参数 - 应该传递单个seq(或null).在尾部位置以外重复是一个错误.

请注意,recur是Clojure中唯一不占用堆栈的循环结构.没有尾调用优化,并且不鼓励使用自调用来循环未知边界.recur是功能性的,它在尾部位置的使用由编译器验证 [强调是我的].

(def factorial
  (fn [n]
    (loop [cnt n acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))))))

我如何使这个Haskell幂函数尾递归？

turboPower a 0 = 1
turboPower a b
    | even b = turboPower (a*a) (b `div` 2)
    | otherwise = a * turboPower a (b-1)

我正在学习圣诞节考试和做一些示例考试的问题,我遇到过这个让我有点难过的问题.

我可以做正常的递归,但是我不能用头尾部来解决如何使用尾递归来编写相同的东西.

常规版:

    (define (factorial X)
      (cond
            ((eqv? X 1) 1)
            ((number? X)(* X (factorial (- X 1))))))

我在向朋友解释我期望Scala中的非尾递归函数比尾递归函数慢,所以我决定验证它.我用两种方式编写了一个很好的旧因子函数,并试图比较结果.这是代码:

def main(args: Array[String]): Unit = {
  val N = 2000 // not too much or else stackoverflows
  var spent1: Long = 0
  var spent2: Long = 0
  for ( i <- 1 to 100 ) { // repeat to average the results
    val t0 = System.nanoTime
    factorial(N)
    val t1 = System.nanoTime
    tailRecFact(N)
    val t2 = System.nanoTime
    spent1 += t1 - t0
    spent2 += t2 - t1
  }
  println(spent1/1000000f) // get milliseconds
  println(spent2/1000000f)
}

@tailrec
def tailRecFact(n: BigInt, s: BigInt …

给定(非二进制)树的以下定义:

sealed trait Tree[+A]
case class Node[A](value: A, children: List[Node[A]]) extends Tree[A]
object Tree {...}

我写了以下折叠方法:

def fold[A, B](t: Node[A])(f: A ? B)(g: (B, List[B]) ? B): B =
  g(f(t.value), t.children map (fold(_)(f)(g)))

这可以很好地用于(除其他外)这个map方法:

def map[A, B](t: Node[A])(f: A ? B): Node[B] =
  fold(t)(x ? Node(f(x), List()))((x, y) ? Node(x.value, y))

问题:有人可以帮助我如何编写上面的折叠尾部递归版本吗？

我有一个天真的游戏循环实现

let gameLoop gamestate =     
    let rec innerLoop prev gamestate =
        let now = getTicks()
        let delta = now - prev
        gamestate 
        |> readInput delta
        |> update delta
        |> render delta
        |> innerLoop delta             

    innerLoop 0L gamestate 

此实现抛出stackoverflowexception.在我看来,这应该是尾递归.我可以像这样做一个工作

let gameLoop gamestate =     
    let rec innerLoop prev gamestate =
        let now = getTicks()
        let delta = now - prev
        let newState = gamestate 
            |> readInput delta
            |> update delta
            |> render delta

        innerLoop now newState

    innerLoop 0L gamestate  

所以我的问题是为什么第一个代码示例抛出stackoverflow异常.

我试图找到二叉树的尾递归折叠函数.鉴于以下定义:

// From the book "Functional Programming in Scala", page 45
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

实现非尾递归函数非常简单:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B =
  t match {
    case Leaf(v)      => map(v)
    case Branch(l, r) => 
      red(fold(l)(map)(red), fold(r)(map)(red))
  }

但现在我正在努力寻找尾递归折叠函数,以便@annotation.tailrec可以使用注释.

在我的研究过程中,我发现了一些例子,其中树上的尾递归函数可以例如使用自己的堆栈计算所有叶子的总和,然后基本上是a List[Tree[Int]].但据我所知,在这种情况下它只适用于添加,因为无论您是首先评估运算符的左侧还是右侧都不重要.但对于广义折叠来说,它是非常相关的.为了表明我的意图,这里有一些示例树:

val leafs = Branch(Leaf(1), Leaf(2))
val left = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
val right = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
val …

从Java 8开始,Java不提供Tail-Call Optimization(TCO).在研究它时,我开始知道原因是:

在jdk类中,有许多安全敏感方法依赖于计算jdk库代码和调用代码之间的堆栈帧来确定谁在调用它们.

但是,基于JVM的Scala支持Tail-Call Optimization.Scala在编译时进行尾递归优化.为什么Java不能使用相同的方法？

PS:不确定Java的最新版本(现在的Java 11)现在是否具有TCO.如果有些知道的人也能分享这个,那就太好了.

注意

1. 我知道TCO处于积压状态并且优先级较低,但是想知道为什么Java在编译时不能像Scala那样进行更改.

2. 由于大多数命令式语言都没有Java,因此Java没有尾调用优化.命令式循环是该语言的首选样式,程序员可以用命令式循环替换尾递归.(来源)