Scala 中的尾递归

Question

我有一个关于 scala 尾递归的问题。我写了一个简单的尾递归代码，它接受一个列表并创建一个新的偶数列表。但是由于 scala 无法将元素附加到列表中，所以我的列表是按降序排列的。下面是代码

def listCreator(lists: List[Int]): List[Int] = {
    @tailrec
    def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
        lists match {
            case Nil => accum
            case x :: Nil if (isEven (x) == true) => x :: accum
            case x :: Nil if (isEven (x) == false) => accum
            case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
            case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
        }
    }
    evenListCreator(lists, List()) 
}

我有以下问题

如何在此方法中添加反转列表的语句？
紧跟方法调用的这一行evenListCreator(lists, List())，尾递归是必须的吗？

Answer 1

退货前可以退货

scala> def listCreator(lists: List[Int]): List[Int] = {
     |     @tailrec
     |     def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
     |         lists match {
     |             case Nil => accum
     |             case x :: Nil if (isEven (x) == true) => x :: accum
     |             case x :: Nil if (isEven (x) == false) => accum
     |             case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
     |             case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
     |         }
     |     }
     |     evenListCreator(lists, List.empty[Int]).reverse 
     | }
listCreator: (lists: List[Int])List[Int]

scala> listCreator((1 to 10).toList)
res2: List[Int] = List(2, 4, 6, 8, 10)

scala>

您不需要立即跟进方法调用，但如果您不需要，则需要发送两个参数，一个是列表，第二个是空列表。所以我们只采用整数列表，这样使用的人就不必费心发送空列表了。

你也可以直接做

scala> val list = (1 to 10).toList
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.map(_ * 2)
res8: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

scala>

Answer 2

evenListCreator(lists, List()).reverse 或 evenListCreator(lists.reverse, List())，但在您的情况下，第一种形式更好，因为要反转的列表在调用 evenListCreator
这一行：evenListCreator(lists, List())后面不跟方法调用，它是方法调用。没有它，什么也不会发生，因为您只会定义尾递归函数 (def evenListCreator) 和 return 而不会调用它。

其他一些注意事项

你的停止条件太多了，这个就够了：

@tailrec
def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
  lists match {
    case Nil => accum
    case x :: tail if (isEven (x) == true) => evenListCreator(tail, x :: accum)
    case x :: tail if (isEven (x) == false) => evenListCreator(tail, accum)
  }
}

代码太冗长，我觉得这样更好：

@tailrec
def evenListCreator(lists: List[Int], accum: List[Int]): List[Int] = {
  lists match {
    case Nil => accum
    case x :: tail if isEven (x) => evenListCreator(tail, x :: accum)
    case x :: tail if !isEven (x) => evenListCreator(tail, accum)
  }
}

你也可以这样调用递归函数：

evenListCreator(lists, Nil)

Answer 3

Q1。正如@Mahesh Chand Kandpal 所指出的，您可以在 List 返回之前反转它，或者您可以使用附加方法 accum :+ x 构建列表，而不是前置 ("cons") 方法，x :: accum.

但是在 List 上，cons 方法比 append 方法更有效，因此构建和反转通常更好。

Q2。不。尾递归只是意味着在调用 returns 之后没有其他操作在等待。换句话说，return callMyself() 是尾调用而 return callMyself() + 1 不是。

P.S。我知道这只是一个学习练习，但是，真的......

def listCreator(ints: List[Int]): List[Int] = ints.filter(i => (i&1) < 1)

Scala 中的尾递归

Tail recursion in Scala

scala

tail-recursion