时间戳

首页 > 解决方案 > 进行递归调用，尾递归

scala - 进行递归调用，尾递归

问题描述

我有以下递归函数

trait SequenceGenerator[T] {
  def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = {
    l.flatMap(rule.generate)
  }

  def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {
    number match {
      case 1 => program(seed)
      case a => program(sequenceNumber(seed, a - 1))
    }
  }
}

我想不出一种使sequenceNumber尾递归的方法。

标签： scalarecursion

解决方案

将方法转换为 tailrec 背后的想法是将每个下一个计算步骤放入累加器，然后将此累加器传递回该方法，以便在下一步您可以返回累加器或再次调用此方法，并根据您的步骤修改新的累加器。

所以你会得到这样的东西：

trait SequenceGenerator[T] {

  def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = l.flatMap(rule.generate)

  def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {

    @tailrec
    def tailRec(number: Int, acc: List[T]): List[T] =  number match {
      case 1 => acc
      case a => tailRec(a-1,program(acc))
    }

    tailRec(number,program(seed))

  }

}

但仅供参考，还有一种更先进的构建尾递归的技术，称为Trampoling. 它可以使用scala.util.control.TailCalls例如来实现。

我对这种技术不是很好，但它看起来像这样：

import TailCalls._

trait SequenceGenerator[T] {

  def program(l: TailRec[List[T]])(implicit rule: ProductionRule[T]):TailRec[List[T]] = {
    l.map(_.flatMap(rule.generate))
  }

  def sequenceNumber(seed: TailRec[List[T]], number: TailRec[Int])(implicit rule: ProductionRule[T]): TailRec[List[T]] = {
    number flatMap {
      case 1 => tailcall(program(seed))
      case a => tailcall(program(sequenceNumber(seed, done(a - 1))))
    }
  }

}

sequenceNumber在这里不能标记为tailrec，但它实际上是在“背景”中的tailrec。要获得真实的计算结果，您需要调用sequenceNumber(done(...),done(...)).result

推荐阅读