CODEWITHSUNDEEP
haskellrecursion
zoko
zoko

Reputation: 51

Why is this recursion slow?

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)

Upvotes: 5

Views: 181

Answers (2)

behzad.nouri
behzad.nouri

Reputation: 77951

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 (1):

\> 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]

Upvotes: 2

Dan
Dan

Reputation: 13160

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

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

is not the same thing as

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

In the first case, the two foo functions 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 part of foo a it has already computed, it has to compute the whole thing again.

Upvotes: 0

Related Questions