Haskell中：遞歸地定義的函數的有效計算值

欲計算遞歸定義的函數值r(i,j)，其通過Haskell中：遞歸地定義的函數的有效計算值

r i j | i<0 || j<0 = 0 
     | i==0 && j==0 = 1 
     | otherwise = (i-1) * r (i-2) j + r (i-1) (j-1)

顯然所定義，這些係數的NxN表可以在O(N^2)計算。不幸的是，簡單的評價，像

[[r i j | j <-[0..50]]| i <- [0..50]]

以令人訝異的方式無效（指數複雜性）進行。顯然，Haskell爲每個r i j構建整個遞歸樹，並忽略先前計算的值r (i-1) (j-1)等。

什麼是計算這種表的優雅而有效的方法？

來源

2012-05-17 user1400365

...我不知道haskell，但似乎你想要動態編程。（googleit） – quasiverse

如果您只需要一個值，而不是整個表格可能需要計算遞歸系列的生成函數，則需要記憶，請參閱http://www.haskell.org/haskellwiki/Memoization – fuz

。我不是這方面的專家，但是我曾在關於離散數學/組合的講座中聽說過這個。也許math.stackexchange.com上的朋友可以在這方面幫助你。我與這種數學相關的詞是「本能微積分」，「gosper算法」和「Zeilberger算法」。也許它是有幫助的。 – epsilonhalbe

正如FUZxxl所說，這是一個記憶問題。

r i j | i < 0 || j < 0 = 0 
     | otherwise  = rss !! i !! j 

rss = [[r' i j | j <- [0..]] | i <- [0..]] 
    where r' 0 0 = 1 
     r' i j = (i-1) * r (i-2) j + r (i-1) (j-1)

如果需要精確值高達50的顯表，你可以使用take 51 (map (take 51) rss)，或[[r i j | j <-[0..50]]| i <- [0..50]]如你所提到的。否則，您可以直接致電r或參考rss。

來源

2012-05-17 09:41:56 dave4420

儘管如此，它仍然比它慢，因爲訪問將是O（i + j）。如果將自己限制爲給定大小，則對於O（1）訪問，數組將更合適（惰性數組，非拆箱），並且如果要使用無限制，則trie樹（IntMap）仍然應快於列表名單。 – Jedai

如果你足夠討厭數組庫API，那就用vector來代替。 –

Haskell中：遞歸地定義的函數的有效計算值

回答

相關問題