[Haskell-cafe] Re: Coin changing algorithm

[Okasaki, C. DR EECS]

ChrisK wrote:
 
> During a single evaluation the recursive calls never "collide", so
> unless this overlap is optimized, then the subproblem memoizing won't do
> anything...

Actually, the recursive calls can collide.  For example, if you are trying to make 87 cents with 7 coins, you can make the first 80 cents with four coins using either 50-10-10-10 or 20-20-20-20.  Either way, you'll end up making a recursive call on 7 cents and 3 coins.  Admittedly, however, with this choice of coin denominations, you don't get very many such collisions...
-- Chris