递归(Recorsion)

递归算法里面最经典的两个非fibonacci和hanio莫属了

今天练习就这两数列用python代码实现

斐波那契数列

'''Fibonacci（斐波那契数列）1,1,2,3,5,8,13,25....'''#使用递归#算法复杂度：O(2^n) 注：该递归算法复杂度较高，且运行速度较慢    #定义实现函数def fib(n):    if n <= 1:        return n    else: 　        return(fib(n-1) + fib(n-2))# 获取用户输入 num = int(input("您要输出几项? "))# 检查输入的数字是否正确if num <= 0:    print("输入正数")else:    print("斐波那契数列:")    for i in range(num):        print(fib(i))#输出结果#输出结果您要输出几项? 10斐波那契数列:0112358132134

#使用简单的函数#算法复杂度更低的fibonacci数列#算法复杂为O（n）def fib(n):    num, a, b = 0, 0, 1    while num < n:        print(b)        a, b = b, a + b        n = n + 1    return 'done'#输出结果>>> fib(6)112358'done'

汉诺塔

#递归#算法复杂度：O（2^n）'''设定三根棒子从左到右为：x、y、z思路：第一步：x上的（n-1）个盘子借助 z 到 y上第二步：y上的（n-1）个盘子借助 x 到 z上'''def hanio(n,x,y,z):    if n == 1:        print(x,'-->',z)       #如果只有一层，直接从x移动到z    else:        hanio(n-1,x,z,y)    #将n-1个盘子从x移动到y        print(x,'-->',z)       #最底下的盘子从x移动到z         hanio(n-1,y,x,z)    #将n-1个盘子从y移动到zn = int(input('please input the floor:'))hanio(n,'x','y','z')#输出结果please input the floor:3x --> zx --> yz --> yx --> zy --> xy --> zx --> z