Project Euler 31「硬貨の和」

はじめての再帰関数。
頭の中がグッチャグチャだよ。
何度も無限ループかましちゃったよ。

Problem 31 「硬貨の和」

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である．
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?

coins = [1, 2, 5, 10, 20, 50, 100, 200]
coins.sort(reverse=True)

def hoge(coins, target):
    # 大きい貨幣から順に使っていくイメージ
    cnt = 1 # 1pのみの場合は初めにカウントしておく
    for c in coins[:-1]: # forループは1pを除く
        # 使えるだけ使うパターンから順にやっていく
        for n in reversed(range(target//c)):
            amount = c * (n + 1)
            if amount == target:
                cnt += 1
            else:
                # 残りの貨幣と差額を渡して再帰呼び出し
                cnt += hoge(coins[coins.index(c)+1:], target-amount)
    return cnt

print(hoge(coins, 200))

コンガラガル。サイキコワイ。