我一直在研究递归和 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 实现是我的问题陈述的缩影。