L23递归

铃铛

斐波那契数列的实现



黄金分割比例
斐波那契数列中的相邻两个数前一个数除以后一个数得到的比值越来越接近黄金分割比0.618：1
把数据结构模拟成斐波那契数列可以获得黄金分割比例的数值安排


练习：假设我们需要求出经历20个月后，总共有多少对小兔崽子？（迭代vs递归）
迭代：
def hase(n):
    result={}
    for i in range(1,n+1):
        if i==1 or i ==2:
            result[i]=1
        else:
            result[i]=result[i-1]+result[i-2]
    return result

summe=hase(20)
print(summe[20])
def fab(n):
    n1=1
    n2=1
    n3=1
    if n<1:
        print('input error')
        return -1
    while n-2:
        n3=n2+n1
        n1=n2
        n2=n3
        n-=1
    return n3
result=fab(20)
if result!=-1:
    print('总共有%d对小兔崽子诞生'%result)

递归：
def hase(n):
    if n>2:
        return hase(n-1)+hase(n-2)
    else:
        return 1
summe=hase(20)
print(summe)

def fab(n):
    if n<1:
        print('input error')
        return -1
    if n==1 or n==2:
        return 1
    else:
        return fab(n-1)+fab(n-2)
   
result=fab(20)
if result !=-1:
    print('总共有%d对小兔崽子诞生'%result)

递归算法：分治思想