递归（coded with python3）

1.青蛙跳台阶，一共n阶，可以一次跳一阶或两阶，一共多少种跳法。

def sumWays(n):
    if n==0 or n==1:
        return 1
    else:
        return(sumWays(n-1)+sumWays(n-2))
if __name__ == '__main__':
    for x in range(1,10):
        print(sumWays(x))

result:

weehaaMBA:Downloads huangyong$ python3 h1.py 
1
2
3
5
8
13
21
34
55

这应该是最简单的递归了。
递归，先列出n=1,2,3的前三种情况，便于分析。
2.当上题中可以跳1～n阶时
f(1)=1
f(2)=2=f(1)+f(0)
f(3)=f(2)+f(1)+f(0)=4

可以推出 f(n)=2*f(n-1)

def sumWays(n):
    if n==0 or n==1:
        return 1
    else:
        return 2*sumWays(n-1)
if __name__ == '__main__':
    for x in range(1,10):
        print(sumWays(x))

result:

weehaaMBA:Downloads huangyong$ python3 h1.py 
1
2
4
8
16
32
64
128
256

硬币兑换，给定一些面值的硬币和一个具体钱数，问少能用几个硬币兑换。例如给定硬币面值coins=[1,2,5] amount=11，return 3（5+5+1）02:coins=[2] amount =3，return -1.

非递归解法：

# coins = [1,2,5]
# amount = 11

# n1 = amount//coins[2]
# n2 = (amount%coins[2])//coins[1]
# n3 = (amount%coins[2]%coins[1])//1

# print(n1+n2+n3)

# 换硬币
def exchangeCoins(coins,amount):
    res = 0
    if len(coins)==0 or amount<coins[0]:
        return -1
    for i,s in enumerate(coins):
        res += amount//coins[-1-i]
        amount = amount%coins[-1-i]
    if amount != 0:
        return -1
    return res
if __name__ == '__main__':
    print(exchangeCoins([1,2,5],14))