如何实现TCO的递归

Question

我一直在研究递归和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链接的链接.可以肯定的是,相当多的人可以编写比我更好更简洁的尾递归代码.我仍然认为通常TCO更冗长(例如,Factorial和Fibonacci尾调用递归有额外的参数,累加器.)然而,需要TCO来防止堆栈溢出.我想知道你将如何接近TCO和递归.在此线程中,Akermann与TCO的Scheme实现集中体现了我的问题陈述.

Answer 1

您是否有可能使用术语"尾调用优化",实际上您实际上要么意味着以迭代递归方式编写函数,要么继续传递样式,以便所有递归调用都是尾调用？

实施TCO是语言实施者的工作; 一篇论文讲述了如何有效地完成它是经典的 Lambda:终极GOTO论文.

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