如何实现TCO‘’ed递归

Question

我一直在研究递归和总拥有成本。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
      }
  }

这篇文章很短，我不需要花太多时间在这上面。然而，当我试图在尾部调用递归中做到这一点时，以降低总拥有成本。我不得不花费大量的时间，代码变得非常冗长。我不会为了节省空间而放置整个代码。Here is a link to git repo link。可以肯定的是，有相当多的人可以写出比我写得更好、更简洁的尾递归代码。我仍然相信总体上TCO更加冗长(例如，阶乘和斐波那契尾部调用递归有额外的参数，累加器)。然而，需要TCO来防止堆栈溢出。我想知道您将如何处理TCO和递归。在this thread中使用总拥有成本的阿克曼的方案实现概括了我的问题陈述。

Answer 1

你有没有可能使用术语“尾部调用优化”，而实际上你的意思是用迭代递归风格或继续传递风格编写函数，这样所有的递归调用都是尾部调用？

实现总体拥有成本是语言实现者的工作；关于如何有效地实现它的一篇论文是经典的Lambda: the Ultimate GOTO论文。

尾部调用优化是你的语言的计算器会为你做的事情。另一方面，你的问题听起来像是在问如何以特定的风格表达函数，以便程序的形状允许求值器执行尾调用优化。

Answer 2

正如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

Answer 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))