Why is this recursion slow?

Question

I am trying to solve a problem:

How many ways to get $ 50 using only 1c, 5c, 10c, 25c or 50c coins?

Here is my code:

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) 

Turns out my recurse function recurse slow, maybe quadratic or worse. But I don’t understand why, since it looks like a fibonacci list

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

Answer 1

The problem with recursion is that you need to be careful about the exponential branch or have exponential memory-printing; and also a record of a tail recursive function is usually less expressive.

You can get around the whole load of recursion by dynamically programming; which has a very efficient implementation in Haskell using the right fold:

 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 

then

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

or as in the 31st problem of Project Euler ⁽¹⁾ :

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

A less effective alternative would be to use immutable non-strict (boxed) arrays:

 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) The problem has already been sent elsewhere in stackoverflow; see Using dynamic programming in Haskell? [Warning: ProjectEuler 31 solution inside]}

Answer 2

You are right, this is quadratic time. The problem is that

 +------------+ vv foo a = bar (foo a) 

- this is not the same as

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

In the first case, the two functions foo refer to the same object, but in the second, the result of foo refers to the same object. So, in the first case, if bar wants to refer to the part of foo a that it has already calculated, it must calculate all this again.