代码之家 › 专栏 › 技术社区 › Srinivas

Scala中的尾部递归

tail-recursion scala

Srinivas · 技术社区 · 7 年前

我有一个关于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())

3 回复 | 直到 7 年前

Mahesh Chand 7 年前

您可以在退回之前反转。

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>

您不需要立即执行方法调用,但如果不执行,则需要发送两个参数,一个是list,另一个是空list。所以我们只取整数列表,这样使用的人就不用麻烦发送空列表了。

你也可以直接做

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>

Frederic A. 7 年前

evenListCreator(lists, List()).reverse 或 evenListCreator(lists.reverse, List()) ,但在您的情况下,第一种形式更好,因为调用 evenListCreator
该行: evenListCreator(lists, List()) 不遵循方法调用是方法调用。没有它,一切都不会发生,因为您只需要定义尾部递归函数( def evenListCreator )不打电话就回来。

其他注意事项

您有太多停止条件,这就足够了:

@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)

jwvh 7 年前

问题1.您可以反转 List 在返回之前,正如@Mahesh Chand Kandpal所指出的,或者可以使用append方法构建列表, accum :+ x ,而不是预挂(“cons”)方法, x :: accum .

但是在一个 列表

不是。尾部递归只是意味着在调用返回后没有其他操作等待。换句话说, return callMyself() 是尾声,但是 return callMyself() + 1 不是。

P、我知道这只是一个学习练习,但是,真的。。。

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