ペンスを再帰で数える
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)