内容来源于网络，本人只是在此稍作整理，如有涉及版权问题，归小甲鱼官方所有。

练习题（来自小甲鱼官方论坛）

编程题

0.使用递归编写一个十进制转换为二进制的函数（要求采用“除2取余”的方式，结果与调用bin（）一样返回字符串形式）

答：

def binB(num):
    # 剥洋葱思路
    # 每一次都要做两件事 num // 2; num % 2
    # 先预设一个空字符串: result
    result = ''

    if num:
        # 开始剥洋葱 num // 2，直到洋葱皮剥完为止
        # 当到最后一层（num = 1 ）
        # 开始把洋葱还原，返回 num % 2, 有点类似于出栈
        result = binB( num // 2)
        return result + str(num % 2)
    else:
        # 还原到最外面（实际是在剥到最后一片式，还原回去所有的result），出结果
        return result

print(binB(8))

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)
        get_digits(n // 10)

get_digits(123)
print(result)

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

答：

def huiwen(temp,start,end):
    if start > end:
        return 1
    else:
        if temp[start] == temp[end]:
            return huiwen(temp,start+1,end-1)
        else:
            0

temp = input('请输入一段文字：')
length = len(temp)
end = length-1
if huiwen(temp,0,end):
    print('%s是一个回文字符串！'%temp)
else:
    print('%s不是一个回文字符串！'%temp)

3.使用递归编程求解以下问题：

有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数， 他说比第三个人大两岁,问第三个人，又说比第二个人大两岁，问第二个人，又说比第1个人大两岁。 最后问第一个人，他说是10岁。请问第5个人多大？

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

def age(n):
    if n == 1:
        return 10
    else:
        return age(n-1) + 2

print("第五个人的岁数是%d岁" % age(5))

4.请写下这一节课你学习到的内容：格式不限，回忆并复述是加强记忆的好方式！

• 斐波那契数列：F（1）=1，F（2）=1，F（n）=F(n-1)+F(n-2)(n>=2)

非递归方法：
def fab(n):
    n1,n2,n3 = 1,1,1
    if n<1:
        print('输入有误！')
        return -1
    while (n-2)>0:
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1
    return n3
------------------------------------------
递归方法：
def fab(n):
    if n <= 1:
        return 1
    else:
        return fab(n-1) + fab(n-2)

i = int(input('请指定需要多少项：'))
for j in range(0,i):
    print(fab(j))

• 汉诺塔

def hanoi(n,x,y,z):
    if n == 1:
        print(x,'->',z)
    else:
        hanoi(n-1,x,z,y)#将x上的前n-1个盘移动到y上
        print(x,'->',z)#将x上的n盘移动到z上
        hanoi(n-1,y,x,z)#将y盘上的n-1个盘移动到z上

n = int(input('请输入汉诺塔的层数：'))
hanoi(n,'X','Y','Z')