2

我一直在研究递归和 TCO。似乎 TCO 可以使代码变得冗长并影响性能。例如，我已经实现了接收 7 位电话号码并返回所有可能的单词排列的代码，例如 464-7328 可以是“GMGPDAS ... IMGREAT ... IOIRFCU” 这是代码。

/*Generate the alphabet table*/
  val alphabet = (for (ch <- 'a' to 'z') yield ch.toString).toList

/*Given the number, return the possible alphabet List of String(Instead of Char for convenience)*/
  def getChars(num : Int) : List[String] = {
      if (num > 1) return List[String](alphabet((num - 2) * 3), alphabet((num - 2) * 3 + 1), alphabet((num - 2) * 3 + 2))
      List[String](num.toString)
  }

/*Recursion without TCO*/
  def getTelWords(input : List[Int]) : List[String] = {
    if (input.length == 1) return getChars(input.head)
      getChars(input.head).foldLeft(List[String]()) {
        (l, ch) => getTelWords(input.tail).foldLeft(List[String]()) { (ll, x) => ch + x :: ll } ++ l
      }
  }

它很短，我不必花太多时间在这上面。但是，当我尝试在尾调用递归中执行此操作以获取 TCO 时。我必须花费大量时间并且代码变得非常冗长。我不会摆出整个代码来节省空间。这是 git repo link 的链接。可以肯定的是，你们中的很多人都可以写出比我更好、更简洁的尾递归代码。我仍然相信总体而言 TCO 更冗长（例如阶乘和斐波那契尾调用递归有额外的参数累加器。）但是，需要 TCO 来防止堆栈溢出。我想知道您将如何处理 TCO 和递归。在这个线程中使用 TCO 的 Akermann 的 Scheme 实现是我的问题陈述的缩影。

4

3 回答 3

5

您是否有可能使用“尾调用优化”一词，而实际上您实际上是指以迭代递归样式或继续传递样式编写函数，以便所有递归调用都是尾调用？

实施 TCO 是语言实施者的工作；一篇讨论如何高效完成的论文是经典的 Lambda：Ultimate GOTO论文。

尾调用优化是您的语言评估员将为您做的事情。另一方面，您的问题听起来像是在询问如何以特定样式表达函数，以便程序的形状允许您的评估者执行尾调用优化。

于 2011-12-01T02:55:58.803 回答
4

正如评论中提到的 sclv ，尾递归对于 Haskell 中的这个示例毫无意义。可以使用 list monad 简洁高效地编写问题的简单实现。

import Data.Char
getChars n | n > 1     = [chr (ord 'a' + 3*(n-2)+i) | i <- [0..2]]
           | otherwise = ""
getTelNum = mapM getChars
于 2011-11-23T08:53:08.337 回答
3

正如其他人所说，我不会担心这种情况下的尾调用，因为与输出的大小相比，它不会递归得很深（输入的长度）。在你出栈之前你应该内存不足（或耐心）

我可能会用类似的东西来实现

def getTelWords(input: List[Int]): List[String]  = input match {
   case Nil => List("")
   case x :: xs => {
      val heads = getChars(x)
      val tails = getTelWords(xs)
      for(c <- heads; cs <- tails) yield c + cs
   }
}

如果您坚持使用尾递归，那可能是基于

def helper(reversedPrefixes: List[String], input: List[Int]): List[String] 
  = input match {
    case  Nil => reversedPrefixes.map(_.reverse)
    case (x :: xs) =>  helper(
      for(c <- getChars(x); rp <- reversedPrefixes) yield c + rp,
      xs)
  }

（实际的例程应该调用helper(List(""), input)）

于 2011-11-23T09:11:29.567 回答