ペンスを再帰で数える

Project Eulerの31問目、コインを組み合わせて2ポインドを作るというやつは、再帰を使えばスッキリ書ける。Pythonで書かれたほかの参加者の回答を見てなるほどなぁと思ったので、Rubyでも書いてみた。動的計画法よりも、再帰のほうがスッキリしやすいような気がする。ただ、若干の洞察が含まれていて自明度は低い。

def rec(coins, pence)
  return 1 if coins == [1]
  if pence >= 0
    return rec(coins, pence - coins[-1]) + rec(coins[0...-1], pence)
  end
  return 0
end

coins = [1, 2, 5, 10, 20, 50, 100, 200]
puts rec(coins, 200)