第23、24讲：递归：这帮小兔崽子、汉诺塔

参考代码：

def Dec2Bin(dec):

result = ''

if dec:

result = Dec2Bin(dec//2)

return result + str(dec%2)

else:

return result

print(Dec2Bin(7))

运行结果：111

运行过程：return Dec2Bin(7//2) + str(7%2)，也就是：Dec2Bin(3) + str(1)，即：Dec2Bin(3//2) + str(3%2) + str(1)，即：Dec2Bin(1) + str(1) + str(1)，即：Dec2Bin(1//2) + str(1%2) + str(1) + str(1)，即：str(1) + str(1) + str(1)

1.写一个函数get_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。举例：get_digits(12345)==>[1,2,3,4,5]

解题思路：利用除以10取余数的方式，每次调用get_digits(n//10),并将余数存放到列表中即可。要注意的是结束条件设置正确。

参考代码：

result = []

def get_digits(n):

if n > 0:

result.insert(0, n%10)   #取出个位放列表的位置0

get_digits(n//10)            #去除最后一位

get_digits(12345)

print(result)

2.还记得求回文字符串那道题吗？现在让你使用递归的方式求解，亲还能傲娇的说我可以吗？

解题思路：有好多种方法，不过综合效率来说，小甲鱼的实现方法比较朴素，利用递归每次索引前后两个字符进行对比，当start>end的时候，也正是首尾下标“碰面”的时候，即作为结束递归的条件。

参考代码：

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个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第三个人大2岁。问第三个人，又说比第二个人大两岁。问第二个人，说比第一个人大两岁，最后问第一个人，他说是10岁，请问第5个人多大？

解题思路：利用递归的方法，递归分为回推和递推两个阶段。要想知道第5个人的岁数，需要知道第四个人的岁数，依次类推，推到第一人（10岁），再往回推。

参考代码：

def age(n):

if n == 1:

return 10

else:

return age(n-1) + 2

print('哈哈，我知道了，第五个人的年龄是%d岁，啵啵脆！'% age(5))