# 斐波那契（Fibonacci）数列的递归实现 做为例子
 
# 所经过的月数    1   2   3   4   5    6   7   8   9   10  11  12
# 兔子的总数      1   1   2   3   5   8   13  21  34  55  89  144

# 当前月数的兔子总数是前两个月总数合

# 可以用数学函数来定义：
'''
           { 1, 当 n=1
当  F(n) =   1, 当 n=2
             F(n-1) + F(n-2), 当 n>2
           }
'''
# 假设需要求出经历了20个月后，总共有多少对小兔崽子？ （迭代 vs 递归）

# 迭代实现
print("--迭代实现--")
def fab(n):
    n1 = 1 
    n2 = 1
    n3 = 1

    if n < 1:
        print("输入有误！")
        return -1   
    while (n - 2) > 0:
        n3 = n2 + n1
        # 这里要先n1 = n2。  如果先n2 = n3的话，再n1 = n2，n1的值就不是原来的n2了
        n1 = n2
        n2 = n3
        n -= 1
    return n3
result = fab(20)
if result != -1:
    print("20个月后总共有%d对小兔崽子诞生！" % result)
     

# 递归实现
print("\n--递归实现--")
def fab(n):
    if n < 1:
        print("输入有误！")
        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("20个月后共有%d对小兔崽子诞生！" % result )


# 递归算法在数据结构和算法中被称为分治思想  
# 把复杂的问题分成两个比较复杂的问题，这两个比较复杂的问题还解决不了就再分解成四个比较不那么复杂的问题，若再解决不了就分解成16个一点都不复杂的问题