A-10-递归总结与练习
本帖最后由 高渐飞 于 2018-7-16 15:20 编辑#知识点总结
#(1)递归即函数内部自己调用自己;必须要有正确的返回值；
#(2)每次递归都需要建栈,弹栈,清理,消耗内存，因此当递归无返回值或返回值错误时，会导致代码无休止的运行直到程序崩溃
#(3)斐波那契数列，又称黄金分割数列，兔子序列，F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
#(4)汉诺塔:假设汉诺塔有x，y，z三根柱子，已知柱子x上有n个盘子，盘子大小各不相同呈金字塔状放置；
# 要求将n个盘子从柱子x上移到柱子z上，条件是每次只能移到一个盘子，而且必须永远是大盘子在下小盘子在上的移到状态。
# 将n个盘子从柱子x移到柱子z上，无法直接实现该过程，需借助柱子y；
# 首先，将柱子x上的n-1个盘子移动到柱子y上；
# 然后，将柱子x上最后一个盘子移动到柱子z上；
# 最后，将柱子y上的n-1个盘子移动到柱子z上。
#练习部分
#coding: UTF-8
#1.实现阶乘
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
number = int(input('请输入一个正整数:'))
result = factorial(number)
print("%d 的阶乘是:%d" % (number, result))
#2.用迭代法（循环）实现斐波那契数列，并输出
def fab(n):
n1 = 1
n2 = 1
temp="1 1"
if n < 1:
print('输入有误！')
return -1
else:
print("0-n之间的斐波那契数列为：\n",temp,end=" "),
while (n-2) > 0:
n3 = n1 + n2
n1 = n2
n2 = n3
n -= 1
print(n3,end=" ") #使用end=" "可以避免换行，end默认为"\n"
return n3
num = int(input("请输入数列的层数："))
result = fab(num)
if result != -1:
print('\n总共有%d对小兔崽子诞生！' % result)
#3.用递归法实现斐波那契数列，并输出
def fab(n):
if n < 0:
print("输入有误！")
elif n ==1 or n==2:
return 1
else:
return fab(n-1) + fab(n-2)
num = int(input("请输入数列的层数："))
if num <= 0:
print("请输入正整数！")
else:
print("0-n之间的斐波那契数列为:\n",end=' ')
for i in range(1,num+1):
print(fab(i), end="; ")
#4.汉诺塔
def hanoi(n, x, y, z):
if n == 1:
print(x, ' --> ', z)
else:
hanoi(n-1, x, z, y) #将前n-1个盘子从x移动到y上
print(x, ' --> ', z ) #将最底下的最后一个盘子从x移动到z上
hanoi(n-1, y, x, z) #将y上的n-1个盘子移动到z上
n = int(input('请输入汉诺塔的层数:'))
hanoi(n, 'x', 'y', 'z')
页:
[1]