scala - 如何实现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。我必须花费大量时间，并且代码变得非常冗长。为了节省空间，我不会摆弄整个代码。 Here is a link to git repo link。可以肯定的是，你们中的很多人都可以编写比我更好，更简洁的尾部递归代码。我仍然相信总体而言TCO更冗长（例如，阶乘和斐波那契尾调用递归具有额外的参数，累加器）。然而，需要TCO来防止堆栈溢出。我想知道您将如何处理TCO和递归。 this thread中使用TCO的Akermann的Scheme实施概括了我的问题陈述。

最佳答案

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

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

尾声优化是您的语言评估人员将为您完成的工作。另一方面，您的问题听起来像是您在询问如何以特定样式表示函数，以便程序的形状允许您的评估程序执行尾部调用优化。

关于scala - 如何实现TCO的递归，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8238820/