《零基础入门学习Python》第023、024讲：递归：这帮小兔崽子、汉诺塔

我不是女神ヾ 2022-04-16 04:59 132阅读 0赞

**目录**

动动手

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

1. 写一个函数get\_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。

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

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

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

--------------------

# **动动手** #

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

def Dec2Bin(dec):
        result = ''
        
        if dec:
            result = Dec2Bin(dec//2)
            return result + str(dec%2)
        else:
            return result
    
    print(Dec2Bin(62))

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

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

def age(n):
        if n == 1:
            return 10
        else:
            return age(n-1) + 2
            
    print('哈哈，我知道了，第五个人的年龄是 %d 岁，啵啵脆！' % age(5))

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

（1）斐波那契数列的递归实现：

1，1，2，3，5，8，13，21.....

我们可以用数学函数来定义：

![F(n)=\\left\\\{\\begin\{matrix\} 1, n=1 \\\\ 1, n=2 \\\\ F(n-1)+F(n-2),n>1 \\end\{matrix\}\\right.][F_n_left_begin_matrix_ 1_ n_1 _ 1_ n_2 _ F_n-1_F_n-2_n_1 _end_matrix_right.]

分别用迭代和递归实现：

迭代

def fab(n):
    	n1 = 1
    	n2 = 1
    	n3 = 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:
            print('输入有误！')
            return -1
        elif n == 1 or n == 2:
            return 1
        else:
            return ferber(n-1)+ferber(n-2)

递归算法称为分治思想。

（2）递归实现汉诺塔

![23095111-6018590fcd7241ec8f9c388175248e7d.png][]

对于游戏的玩法，我们可以简单分解为三个步骤：

*  将前63个盘子从a移到b上
 *  将最底下的第64个盘子从a移到c
 *  将b上的63个盘子移到c

问题1：将a上的63个盘子借助c移到b

问题2：将b上的63个盘子借助a移到c

然后：

问题1拆解为：

*          将前62个盘子从a移到c上
 *          将最底下的第63个盘子从a移到b
 *          将c上的62个盘子移到b

问题2拆解为：

*          将前62个盘子从b移到a上
 *          将最底下的第63个盘子从b移到c
 *          将a上的62个盘子移到b

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70][]

[F_n_left_begin_matrix_ 1_ n_1 _ 1_ n_2 _ F_n-1_F_n-2_n_1 _end_matrix_right.]: https://private.codecogs.com/gif.latex?%5Cinline%20F%28n%29%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%201%2C%20n%3D1%20%5C%5C%201%2C%20n%3D2%20%5C%5C%20F%28n-1%29&plus;F%28n-2%29%2Cn%3E1%20%5Cend%7Bmatrix%7D%5Cright.
[23095111-6018590fcd7241ec8f9c388175248e7d.png]: /images/20220416/4b25bd2d66a24d64beacaa20173e783c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTU2MzE4_size_16_color_FFFFFF_t_70]: /images/20220416/dec63ba9aaec4389b16cd3e8ab1b3ad4.png