両替プログラムを再帰手続きで書いてみた

Python

以下、SICPからの問題です。

50¢、25¢、10¢、5¢、1¢の硬貨があるとして、1$の両替の場合の数を計算する手続きを再帰手続きで書いてみましょう。

余談：25¢はクォーター、10¢はダイム、5¢はニッケル、1¢はペニーという通称があります。50¢はハーフダラー？

Pythonで書いてみると、こんな感じでしょうか。

kinds_of_money={1:1, 2:5, 3:10, 4:25, 5:50}

def exchange(amount_of_money, n = 5):
    if(amount_of_money == 0):
        return 1
    elif((amount_of_money < 0) or (n == 0)):
        return 0
    else:
        return exchange(amount_of_money, n - 1) + exchange(amount_of_money - kinds_of_money[n], n)

>>> print exchange(100)
292

ここ最近は、意識的にPythonを使う頻度をあげています。その理由は、少ないタイプ量で簡潔に書けるため、よりアルゴリズムを頭に定着させ、何をしているのかを理解しやすくしたかったからです。また、Webアプリを作成する場合はGoogle App Engineで簡単にWeb環境を手に入れることができます。

まだまだ、断片的な理解ですがとっつきやすく、気に入ってます。