标签: tail-recursion

由于 Scala 开发人员正在学习 IO Monad，因此一般来说，在无法进行尾调用优化的情况下，对于递归来说是必需的 Trampoliing 技术细节，我想知道 Haskell 是如何在本机上避免它的。

我知道 Haskell 是一种懒惰的语言，但是我想知道是否有人可以进一步详细说明。

例如，为什么 ForeverM stackoverflow 在 Scala 中没有？嗯，我可以回答蹦床，我可以在库和博客中找到执行此操作的实际代码。我实际上自己实现了一个基本的蹦床来学习。

它是如何在 Haskell 中发生的？有没有办法稍微解开懒惰，给出一些指示，也许还有有助于更好地理解它的文档？

sealed trait IO[A] {

.....


  def flatMap[B](f: A => IO[B]): IO[B] =
    FlatMap[A,B](this, f) // we do not interpret the `flatMap` here, just return it as a value
  def map[B](f: A => B): IO[B] =
    flatMap[B](f andThen (Return(_)))

}
case class Return[A](a: A) extends IO[A]
case class Suspend[A](resume: () => A) extends IO[A]
case class FlatMap[A,B](sub: IO[A], k: A …

如果我理解正确,可以使用scala.util.control.TailCalls通过使用trampoline来避免非尾递归函数的堆栈溢出.API中给出的示例很简单:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result 

但是,更有趣的情况是,如果要在重新调用之后执行某些操作.我有一个"天真"的因子实现以某种方式运行

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

但这看起来很可怕,我怀疑这是用途.所以我的问题是如何使用TailCalls正确编写阶乘或斐波纳契函数(是的,我知道如何使用累加器来使它们尾递归)？或者TailCalls不适合这种问题吗？

给出以下代码:

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  } …

如何在不使用尾递归的情况下在匿名函数中进行递归？

例如(来自Vanderhart 2010,第38页):

(defn power
  [number exponent]
  (if (zero? exponent)
    1
    (* number (power number (- exponent 1)))))

假设我想将其作为匿名函数执行此操作.由于某种原因,我不想使用尾递归.我该怎么办？例如:

( (fn [number exponent] ......))))) 5 3)
125

我可以使用循环这一点,也可以仅环搭配使用易复发？

我试图理解Haskell中的尾递归.我想我明白它是什么以及它是如何工作的但是我想确保我没有搞砸了.

这是"标准"因子定义:

factorial 1 = 1
factorial k = k * factorial (k-1)

例如,在运行时,factorial 3我的函数会自行调用3次(给它或者拿它).如果我想计算因子99999999,这可能会产生问题,因为我可能有堆栈溢出.在我到达之后,factorial 1 = 1我将不得不在堆栈中"返回"并将所有值相乘,因此我有6个操作(3个用于调用函数本身,3个用于乘以值).

现在我向您介绍另一种可能的因子实现:

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

这个也是递归的.它会称自己为3次.但它没有问题,然后仍然必须"回来"计算所有结果的乘法,因为我已经将结果作为函数的参数传递.

根据我的理解,这就是Tail Recursion的内容.现在,它似乎比第一个好一点,但你仍然可以轻松地拥有堆栈溢出.我听说Haskell的编译器会在后台将Tail-Recursive函数转换为for循环.我想这就是为什么它能够为尾递归功能付出代价呢？

如果这就是原因,那么如果编译器不打算做这个聪明的技巧,那么绝对没有必要尝试使函数尾递归 - 我是对的吗？例如,虽然理论上C#编译器可以检测并将尾递归函数转换为循环,但我知道(至少是我所听到的)目前它没有这样做.所以现在绝对没有必要使函数尾递归.是吗？

谢谢!

我有一个家庭作业,要求使用直接递归的函数来查找数组中最左边,最低,负整数的索引.附加要求是函数的参数是数组和大小,无效值的返回值是-999.

我想出了这个:

int LowIndexMinNeg(int src[], int size)
{
    if (size == 0)
       return -999;
    int index = LowIndexMinNeg(src, size - 1);

    if (index >= 0)
       return (src[size - 1] < src[index]) ? (size - 1) : index;
    else
       return (src[size - 1] < 0) ? (size - 1) : index;
} 

它有效,满足要求,并得到我充分的信任.这可以用尾递归实现吗？

在我看来,因为你必须从递归调用中获取结果,以便在比较中使用它来决定你是否通过那个或更新它,这是不可能的,但是递归仍然将我的大脑联系起来可能有一些我很想念的东西.

注意:我的家庭作业已经上交并评分.

可能重复:
为什么JVM仍然不支持尾调用优化？

我在网上看到了很多不同的答案,所以我想我会问专家.

可能重复:
是否存在无法使用尾递归写入的问题？

根据我的理解,尾递归是一种优化,当递归调用不需要来自它将发送垃圾邮件的递归调用的信息时,您可以使用它.

那么可以使用尾递归实现所有递归函数吗？像DFS这样的东西,你需要最内层的孩子在父母可以之前返回？

关于GCC手册,

-foptimize同胞通话

优化兄弟和尾部递归调用.

例如,我知道尾递归调用

int sum(int n){return n == 1？1:n + sum(n-1); }

然而,兄弟姐妹的意思是什么？

据我所知,递归非常优雅,但在OOP和程序编程方面效率不高(参见精彩的"High Order perl",Mark Jason Dominus).我有一些信息,在函数式编程递归中很快 - 保持其优雅和简洁.有人可以确认并可能放大这个吗？我正在考虑XSLT和Haskell(我的下一个语言学习列表的高位)

谢谢

丹尼尔