笔记
斐波那契数列
汉诺塔
有64个盘子，三根柱子（从左至右依次为x,y,z柱）。要求将这64个盘子从x移动到z上。
解决思想：
首先，将三根柱子依次分为起始柱，辅助柱和目标柱。在移动过程中，这三个柱子不是绝对不变的，而是会不断改变的。(移动多个盘子时，先确定好是从哪个柱子移到哪个柱子，即先确定起始柱和目标柱，然后剩下的柱子作辅助柱)
把问题分为三个简单步骤：1、将63个盘子从x借助z移动到y上（此时x:起始柱，y:目标柱，z:辅助柱）；
2、将最后一个盘子从x移动到z上；
3、将1中的63个盘子从y借助x移动到z上（此时x:辅助柱，y:起始柱，z:目标柱）。
那么，第二个步骤显然一步就可以完成，而第一、二步骤实际上又是两个需要细分的问题，又可以各自分为三个简单步骤：
问题一：将63个盘子从x（借助z）移动到y上：
1、将62个盘子从x借助y移动到z上；
2、将最后一个盘子从x移动到y上；
3、将1中的62个盘子从z借助x移动到y上。
问题二：将（1中的）63个盘子从y（借助x）移动到z上：
1、将62个盘子从y借助z移动到x上；
2、将最后一个盘子从y移动到z上；
3、将1中的62个盘子从x借助y移动到z上。
依此类推，可以不断细分到只移一个盘子的最简单的情况。
代码实现：
def hanoi(n,x,y,z):
#n为整型，x,y,z为字符(传入的实参表示柱子的名字)(形参中的x,y,z分别对应起始，辅助，目标柱)
if n == 1:
print(x,'-->',z)
else:
hanoi(n-1,x,z,y)#将前n-1个盘子从x移动到y上
print(x,'-->',z)
hanoi(n-1,y,x,z)#将这n-1个盘子从y移动到z上
课后作业
动动手：
0. 使用递归编写一个十进制转换为二进制的函数（要求采用“取2取余”的方式，结果与调用bin()一样返回字符串形式）。
def Dec2Bin(dec):
result = ''
if dec:
result = Dec2Bin(dec//2)
return result + str(dec%2)
else:
return result
1. 写一个函数get_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。举例：get_digits(12345) ==> [1, 2, 3, 4, 5]
def get_digits(n):
list1 = []
if n:
list1 = get_digits(n//10)
return list1.append(n%10)
else:
return list1
2. 还记得求回文字符串那道题吗？现在让你使用递归的方式来求解，亲还能骄傲的说我可以吗？
def is_palindrome(n, start, end):
if start > end:
return 1
else:
return is_palindrome(n, start+1, end-1) if n[start] == n[end] else 0
string = input('请输入一串字符串：')
length = len(string)-1
if is_palindrome(string, 0, length):
print('\"%s\"是回文字符串!' % string)
else:
print('\"%s\"不是回文字符串!' % string)
3. 使用递归编程求解以下问题：
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？
def age(n):
if n == 1:
return 10
else:
return age(n-1) + 2