2012-07-27 93 views
9

作爲一名Scala新手,我正在閱讀書籍,文檔並嘗試解決http://aperiodic.net/phil/scala/s-99/上發現的問題。看起來正確Scala代碼基於不可變值(val)和遞歸,而不是循環和變量,以便使並行性更安全並避免使用鎖。Scala新手:遞歸和stackoverflow錯誤

例如,對於鍛鍊P22一個可能的解決方案(http://aperiodic.net/phil/scala/s-99/p22.scala)是:

// Recursive. 
def rangeRecursive(start: Int, end: Int): List[Int] = 
if (end < start) Nil 
else start :: rangeRecursive(start + 1, end) 

當然這個代碼是緊湊,看起來聰明,但,當然,如果遞歸的數量很多,你會面對一個StackOverflow錯誤(rangeRecusrsive(1,10000),例如沒有JVM調優)。如果您查看List.range(https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1)中內置的源代碼,您會看到使用循環和變量。

我的問題是如何管理Scala學習東西的影響,它促進vals和遞歸,知道這樣的代碼可能因遞歸次數而中斷?

+0

Scala編譯器足夠聰明,可以在[trampoolined](http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html)尾遞歸(JVM)中編譯尾遞歸調用不支持TCE),這不會導致stackoveflow。如果你想確定,你的代碼是尾遞歸的,添加@tailrec註釋到方法簽名 – 2012-07-27 10:53:14

回答

11

關於Scala的好處是您可以輕鬆進入它。開始時,您可以編寫循環,並隨着您對該語言的使用變得更加舒適,使用遞歸進行更多操作。你不能用更純粹的功能語言如Clojure或Haskell來做到這一點。換句話說,你可以適應不變性和val,然後繼續遞歸。

當你從遞歸開始時,你應該查找尾調用遞歸。如果遞歸調用是函數中的最後一個調用,那麼Scala編譯器會將其優化爲字節碼中的循環。這樣,你就不會得到StackOverflowError。此外,如果您將@tailrec註釋添加到您的遞歸函數中,編譯器會警告您函數是否不是尾調用遞歸。

例如,您問題中的函數不是尾調用遞歸。它看起來像rangeRecursive的調用是該函數中的最後一個,但是當此調用返回時,它仍然必須將start附加到調用的結果。因此,它不能是尾調用遞歸的:它在調用返回時仍然需要工作。

+0

謝謝,所以最終的目標是使尾遞歸函數,而不僅僅是遞歸函數,對嗎? – Brice 2012-07-27 11:15:42

+0

@Brice儘可能多的,是的。有時候這是不可能的,但往往是這樣。在這些情況下,您可以獲得性能改進,並且不必擔心堆棧溢出問題。 – jqno 2012-07-27 11:17:53

1

如果您重寫上面的代碼以使其成爲尾遞歸,編譯器會將代碼優化爲while循環。另外,您可以使用@tailrec註釋在註釋的方法不是尾遞歸時發生錯誤。從而讓你知道「你什麼時候做對了」。

3

下面是一個使該方法尾遞歸的示例。 @tailrec註釋是不必要的,編譯器會在沒有它的情況下進行優化。但是讓它在編譯器無法執行優化時會標記錯誤。

scala> def rangeRecursive(start: Int, end: Int): List[Int] = { 
    | @scala.annotation.tailrec 
    | def inner(accum : List[Int], start : Int) : List[Int] = { 
    |  if (end < start) accum.reverse 
    |  else inner(start :: accum, start + 1) 
    | } 
    | 
    | inner(Nil, start) 
    | } 
rangeRecursive: (start: Int,end: Int)List[Int] 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

它使用所謂的「累加器傳遞風格」,其中中間結果被累積,並傳遞給在遞歸下一步驟的常用技術。最下面的步驟是負責返回累計結果。在這種情況下,累加器恰好向後建立其結果,因此基本情況必須將其倒轉。

+0

還有另外一種方法來做你在那裏做的事,'內部(start :: accum,start + 1)'不使用反向。這可能是這樣的:'內部(accum :::列表(開始),開始+ 1)'我只是不知道什麼可能會更昂貴的編譯器。 – 2016-07-24 19:01:26

+0

我自己找到了答案。我的另一個解決方案在性能方面非常糟糕。沒關係。 – 2016-07-24 19:06:15

1

這裏是詹姆斯IRY的答案的替代,具有相同的行爲:

def rangeRecursive(start: Int, end: Int): List[Int] = { 
    def inner(start : Int) : Stream[Int] = { 
     if (end < start) Stream.empty 
     else start #:: inner(start + 1) 
    } 

    inner(start).toList 
} 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

這不會引發StackOverflowError因爲Stream.cons - 運算符(#::)存儲引用的尾巴。換句話說,在調用stream.toList之前不會計算流元素。

在我看來,這是比蓄電池模式更具有可讀性,因爲它最接近天真的初始算法(只是Stream.empty取代::通過#::Nil)。另外,不需要accum.reverse,這很容易被遺忘。

+0

我在我的代碼中使用這種模式,但我很好奇爲什麼'內部(開始).toList'不會給stackOverflowError。 =>因爲它不是一個遞歸構造? – BlueSky 2017-05-22 23:36:11

+0

'#::'操作符將右側作爲函數而不是值。 'inner(start).toList'將使用循環遍歷所有值。下一個值是在該循環的每次迭代中計算的。 – 2017-05-23 09:53:33