Why is this recursion slow?

Question

I'm trying to solve the problem:

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

Here's 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)

It turns out that my recurse function is slow, maybe quadratic time or worse. But I don't understand why, since it looks similar to the fibonacci list

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

Answer 1

The problem with recursion is that care needs to be taken not to branch exponentially or have exponential memory foot-print; and also writing a tail recursive function is usually less expressive.

You can bypass the entire recursion overhead by dynamic programming; which has a very performant implementation in Haskell using a 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 31st problem of Project Euler ⁽¹⁾:

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

A less efficient 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 is already posted elsewhere on stackoverflow; see Using dynamic programming in Haskell? [Warning: ProjectEuler 31 solution inside]}