なぜこの再帰は遅いのですか？

Question

私は問題を解決しようとしている：

だけ1C、5C、10C、25C、50Cまたはコインを使用して$ 50を得るためにそこにあるどのように多くの方法？

ここに私のコードです：

main = print $ coinCombinations [1,5,10,25,50] !! 5000 

coinCombinations coins = foldr recurse (1 : repeat 0) coins 
    where recurse a xs = take a xs ++ zipWith (+) (drop a xs) (recurse a xs) 

それは多分次の時間か悪いか、私のrecurse機能が遅いことが判明しました。しかし、私はそれが

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Answer 1

フィボナッチリストに似ていますので、再帰の問題はケアが指数関数的に分岐または指数メモリフットプリントを持ってしないように注意する必要があるということである、なぜ理解していません。また、テール再帰的な関数を書くことは、通常は表現力がありません。

動的プログラミングによって再帰オーバーヘッド全体を回避することができます。これは右の折り目を使用してHaskellのに非常にパフォーマンスの実装を有する。

count :: (Num a, Foldable t) => t Int -> Int -> a 
count coins total = foldr go (1: repeat 0) coins !! total 
    where 
    go coin acc = out where out = zipWith (+) acc $ replicate coin 0 ++ out 

次いで：31st problem of Project Euler^で

\> count [1, 5, 10, 25, 50] 5000 
432699251 

又は（1）：

\> count [1, 2, 5, 10, 20, 50, 100, 200] 200 
73682 

以下無効な非厳密（ボックス化）の配列を使用するのが効率的な方法です：

import Data.Array (listArray, (!)) 

count :: (Num a, Foldable t) => t Int -> Int -> a 
count coins total = foldr go init coins ! total 
    where 
    init = listArray (0, total) $ 1: repeat 0 
    go coin arr = out 
     where 
     out = listArray (0, total) $ map inc [0..total] 
     inc i = arr ! i + if i < coin then 0 else out ! (i - coin) 

---

_{（1）問題はすでにstackoverflowの上のどこかに掲載されています。 Using dynamic programming in Haskell? [Warning: ProjectEuler 31 solution inside]}

Answer 2

あなたは正しいです、これは二次的な時間です。問題は

​​

は、最初のケースで

foo a = r 
      +-------+ 
      v  v 
    where r = bar r 

と同じものではないということである二つfoo機能が同じオブジェクトを参照するが、第二に、fooの結果同じオブジェクトを指します。したがって、最初のケースでは、barが既に計算されたfoo aの部分を参照したい場合、それは再びすべてを計算しなければなりません。