SICP iteration solution

sicp_coin.py

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

def cc_rec(amount, kinds_of_coins = 5):
    if amount == 0:
        return 1
    elif amount < 0 or kinds_of_coins == 0:
        return 0
    else:
        return cc_rec(amount, kinds_of_coins - 1) + \
            cc_rec(amount - first_denom[kinds_of_coins], kinds_of_coins)

def cc_iter(amount, kinds_of_coins = 5):
    count = 0
    stack = []
    while stack or amount > 0:

        # Traverse cc_rec(amount, kinds_of_coins - 1)
        while kinds_of_coins > 0:
            stack.append((amount, kinds_of_coins))
            kinds_of_coins -= 1
        while stack:
            _amount, _kinds_of_coins = stack.pop()
            # generate `amount - first_denom[kinds_of_coins]`
            # and  `kinds_of_coins`
            amount = _amount - first_denom[_kinds_of_coins]
            kinds_of_coins = _kinds_of_coins
            if amount < 0:
                continue
            elif amount == 0:
                count += 1
            break

    return count

for n in range(1,100):
    a1=cc_rec(n,1)
    a2=cc_iter(n,1)
    print a1==a2