斯卡拉的尾遞歸

Question

我有一個關於斯卡拉尾遞歸的問題。我寫了一個簡單的尾遞歸代碼，它接受一個列表並創建一個新的偶數列表。但由於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()) 
} 

我有以下幾個問題

1. 我如何可以添加逆轉這種方法中的列表中的語句？

2. 這條線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

1. evenListCreator(lists, List()).reverse或evenListCreator(lists.reverse, List())，但在你的情況下，第一種形式是作爲列表逆轉將最有可能是電話後短至evenListCreator
更好
2. 這一行：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) 

Answer 3

Q1。正如@Mahesh Chand Kandpal指出的那樣，您可以在List之前反轉List，或者您可以使用追加方法accum :+ x而不是預先掛鉤（「cons」）方法x :: accum構建列表。

但是在List上，cons方法比append方法更高效，所以通常建立和反向更好。 Q2302。不，尾遞歸只是意味着在調用返回後沒有其他操作正在等待。換句話說，return callMyself()是一個尾呼，但return callMyself() + 1不是。

P.S.我知道，這僅僅是一個學習的過程，但是，真的...

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