浅谈递归思想

拼搏现实的明天。 2022-04-02 16:12 306阅读 0赞

### 文章目录 ###

*   *  前言
     *  递归的形态
     *  归纳法
     *  递归的思想
     *  递归思想的练习
     *   *  棋盘放麦粒
         *  汉诺塔问题
         *  赏金问题
         *  归并排序
     *  总结

## 前言 ##

如果一谈到“递归”你的脑海就浮现出“自己调用自己”，我想说：“你可能并不懂递归”。当然了，这仅仅是个人鄙见。许多时候，递归确实在“自己调用自己”。我们知道这个道理吧，想用递归解决实际问题却又犯难了——怎么就写不出代码来了呢？

我想异于网上千篇一律文章的讲法，小小的别开生面一回，用自己认为容易理解的方式来阐述递归思想。当然啦，如同标题所说，只能**浅谈**而已。因为，我并不认为自己已经很懂。

## 递归的形态 ##

如前言所说，大多数时候递归是**自己调用自己**。其形式应该如下：

# 示例一
    def print_alpha():
        print("z")
    
        print_alpha()  # 在自己的内部调用自己
    
    if __name__ == "__main__":
        print_alpha()

然而这样的递归并不可取。尽管上边代码的效果与一个死循环一样：

# 示例二
    def print_alpha():
        while True:
            print("z")
    
    if __name__ == "__main__":
        print_alpha()

但因为**递归过程中会保留过程中产生的各种数据，十分耗费系统资源**，所以一般编程语言会限制递归的深度。拿Python为例，运行示例一的代码能看到解释器抛异常如下：

RecursionError: maximum recursion depth exceeded while calling a Python object

所以递归的另一个重点在于：需要一个出口，一个可以**退出递归的出口**。

就好像这样：

def print_alpha(num):
        # 递归出口
        if num <= 0:
            return
        
        print("z")
    
        print_alpha(num-1)
    
    if __name__ == "__main__":
        # num 为打印字母的次数
        print_alpha(num=10)

## 归纳法 ##

现在，我想说说高中数学涉及到的归纳法。

高中学习数列的时候老师应该会先讲一个名为**归纳法**的东西引我们入门，不知各位还记不记得。我是印象深刻的，因为这玩意儿简单好用实在（刚学数列的时候不存在特别难题），但问题是：考试不让用。老师说归纳法只能用来分析题，要证明啊计算啊什么的都得用公式。就不管你是等差求和还是等比求和了。

好，有请著名的斐波拉契数列登场：

1 , 1 , 2 , 3 , 5 , 8 , 13 , . . . 1, 1, 2, 3, 5, 8, 13, ... 1,1,2,3,5,8,13,...

进入提问环节：第8个数应该是多少？

题不存在难度，相信大家很快得出答案为21。为什么呢？因为通过观察发现，从第三个数开始，它的值永远等于前面两个数的和。所以第8个数就应该是： 8 + 13 = 21 8 + 13 = 21 8\+13=21。**这样一个我们思考的过程就是归纳法。**

## 递归的思想 ##

编程中的递归就是数学中的归纳法演变过来的。我们通过发现的规律，将场景演化成代码。

这里还是说斐波拉契数吧。如何用代码计算斐波拉契数列中的第n个数的值呢？回忆一下归纳法中斐波拉契数的规律：**a. 第一、二个数总为1；b. 从第三个数开始，它的值永远等于前面两个数的和。**

def fibonacci(no):
        # a. 第一、二个数总为1
        if no in (1, 2):
            return 1
        
        # b. 从第三个数开始，它的值永远等于前面两个数的和。
        return fibonacci(no-1) + fibonacci(no-2)
    
    if __name__ == "__main__":
        print(fibonacci(no=8))  # 输出：21

有没有体会到递归的强大呢？可以看出，在求第8个数的值的时候，代码并没有关心第一个数的值是什么，第二数的值是什么，它只知道，**我的值总是前两个数的总和，其它的，不在意**。但要清楚，由于第一二个数不在此规律中，所以单独拿出来处理。

现在，不要试图在脑海中计算`fibonacci(no-1)`的结果是什么，`fibonacci(no-2)`的结果又是什么。这真的很不 **“递归”**。写递归代码的要点在于：**总是关心事物间的规律，放弃对过程的探索。** 对过程的探索是归纳法该做的事儿，递归应该是直接使用归纳法得出的结果。

可能你还不明白上一段最后一句话的意思。举个很简单的例子：现下我们需要斐波拉契数列中第100位数的数值。归纳法要怎么用呢？是不是应该先求出第8位数，然后根据第7、8位数求出第9位，之后是第10位、11位…直到有了第98位数和第99位数我们才松了一口气：终于可以求第100位数了。

但我们利用递归写好的代码需要改动吗？不需要，因为第100位数也符合 “前面两个数的和” 这样的规律。事实上递归的好处已经显而易见了，就是为了**更容易地写出代码**。之所以我们看到代码中有递归或者需要用递归来解决问题的时候会发怵，大部分原因不是题太难，而是我们把注意力放在了“过程”，企图用递归把这个“过程”写出来。

## 递归思想的练习 ##

关于利用递归解决问题的编程题很多，网上随处可见，我收集了一些简单题来锻炼递归思想。区别于其他讲述递归的文章，他们总是把重心放在了归纳法上，或者递归、归纳法一起上，让读者一阵眩晕。以下我将只说明从递归思想到实现代码的过程，如果让你觉得很神奇想了解里边的原理，不妨去鉴赏其他网友的文笔。

### 棋盘放麦粒 ###

> 这是一个很有名的和数学相关的故事，讲的是一位国王打算奖赏他的臣子。臣子说：那就奖赏我一些麦粒吧。国际象棋盘上的第一个格子放1粒麦粒，第二个格子放2粒，第三个格子4粒，以此类推8、16…直到放满64个格子。

故事中国王认为这是很容易的事儿，实际操作的时候却发现全国的麦粒加起来都不够这小小棋盘。那么到底需要多少麦粒才能满足臣子的要求呢？

首先，通过归纳法寻找规律，我们可以发现1、2、4、8、16就是一组等比数列，所以第n位上的数字值为： 2 n − 1 2^\{n-1\} 2n−1。

现在我们要写一个计算麦子总数的函数（`get_wheat_total`）。既然这个函数是计算麦子总数的，那么`get_wheat_total(n-1)`肯定等于前面n-1个格子的麦粒数总和了，而第n位的麦子数是 2 n − 1 2^\{n-1\} 2n−1。所以n个格子的麦粒总是就是：`get_wheat_total(n-1) + 2**(n-1)`。既然是递归，我们还得考虑递归的出口，最简单的、也最显而易见的“出口”就是当n=1的时候，返回1。所以代码如下：

def count_wheat_total(n):
        if n == 1:
            return 1
        
        return count_wheat_total(n-1) + 2**(n-1)
    
    if __name__ == "__main__":
        total = count_wheat_total(n=64)
        print(total)

### 汉诺塔问题 ###

汉诺塔问题也来源于一个有趣的故事。最后在数学家的手里演变成了经典数学题，大致是这样：

> 有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
> 
> 1.  每次只能移动一个圆盘；
> 2.  大盘不能叠在小盘上面。  
>     提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。  
>     ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]

为方便语言叙述，我们做这样设置：最小盘子为1号，依次编号，最后最大的盘子（也就是在最底下那个）编号为n。由于大盘子不能放在小盘子上，并且每次只能移动一个圆盘，所以n号盘子应该最先定下位置——也就是需要最先到达C杆。那怎样才能最先定下位置呢？是不是需要这样一个场景：1~n-1编号的盘子都在B杆上，编号n的盘子在A杆上，这样一来就可以直接把n号盘子放在C杆上了。像下面这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 1]

所以有了以下代码：

""" n表示盘子个数，from_表示起始杆 buffe表示缓冲杆，to_表示目的杆 """
    def hannoi(n, from_, buffer, to_):
        # 如果只有一个盘子，则直接从A挪到C
        if n == 1:
            print(from_, "-->", to_)
            return
    
        # 将编号为1~n-1的盘子从A全部挪到缓冲区B
        hannoi(n-1, from_, to_, buffer)
        # 将A杆上最后剩下的编号为n的盘子从A挪到C
        hannoi(1, from_, buffer, to_)
        # 将B杆上留下的n-1个盘子从缓冲区B挪到C
        hannoi(n-1, buffer, from_, to_)
    
    if __name__ == "__main__":
        hannoi(3, "A", "B", "C")

### 赏金问题 ###

> 现有1元、2元、5元、10元的纸币无数，用这些面额的纸币随意拼凑出10元，一共有多少种方法？

赏金问题比前面两个复杂一些，因为涉及到循环，但思考过程是相通的。

我们可以设置一个总额度total为10，让它自己去盒子里取钱。如果取到1元，那么它还需要9元；如果取到5元，则还需要5元。放弃考虑第二次、第三次取到的是多少钱，我们只需要关心：当它还需要0元时，取钱的动作就可以终止，因为手上已经凑够10块。代码如下：

import copy
    
    counts = set()  # 计数器
    rewards = [1, 2, 5, 10]  # 各种面额的纸币
    def get_all_methods(total, list_=[]):
        """ total 总面额 list_ 组合方式 """
        # 认为有效组合
        if total == 0:
            # 去重操作
            sortedList = sorted(list_)
            counts.add(tuple(sortedList))
    
    	# 认为无效组合
        if total < 0:
            return
        
        for i in rewards:  # 从盒子里随意取钱的动作
            # 浅拷贝避免python坑
            newList = copy.copy(list_)
            newList.append(i)
            get_all_methods(total-i, newList)
    
    if __name__ == "__main__":
        get_all_methods(10)
        
        print(len(counts))  # 11

### 归并排序 ###

归并排序的核心思想是“分而治之”。实现步骤两步：

*  第一步**分**
 *  第二步**合**

在实现“分”的时候，我们通过递归将一个列表如：`[2, 5, 1, 9]` 切分成一个一个单独的元素，就好像下边代码那样：

def separator_elem(list_):
        if len(list_) == 1:
            return list_
    
        mid = (0 + len(list_)) // 2
        left = separator_elem(list_[:mid])  # 取出mid左边的列表
        right = separator_elem(list_[mid:])  # 取出mid右边的列表
        print(left)
        print(right)
    
    # 输出：
    [2]
    [5]
    [1]
    [9]
    None
    None

最后会有两个**None**，是因为Python函数会在没有明确写明return值的时候默认返回None。注意，我们上边的代码只在`len(list_) == 1`时会返回一个列表，除此之外，函数运行结束之后，默认返回None。

现在我们拿到了单个元素（**不得不提醒一下，这里的每个元素都在分布在单独的一个列表中，马上我们会用到这个特点**），需要考虑如何归并这些元素了。这时候千万不要考虑太多，就拿`[2]`和`[5]`练练手，问题将变成这样：**如何让两个有序列表中的元素合并到一个列表中去，同时保证在新列表中仍然有序？**

x = [2]
    y = [5]
    
    # l, r 分别是x, y列表的索引
    l, r = 0, 0
    tmp = []  # 临时列表，用于存放x, y列表中的元素，且按从小到达的顺序存放
    while True:
        if l >= len(x):
            tmp.extend(y[r:])
            break
        elif r >= len(y):
            tmp.extend(y[l:])
            break
        elif x[l] > y[r]:
            tmp.append(y[r])
            r += 1
        else:
            tmp.append(x[l])
            l += 1

如今我们有了可以独立元素的separator\_elem()函数，也有了可以归并两个有序列表的merge()函数。它们在过程中会擦出怎样的火花我们不管，总之我们结合这两个函数就得到一个完整的归并排序了。

def separator_elem(list_):
        if len(list_) == 1:
            return list_
    
        mid = len(list_) // 2
        left = separator_elem(list_[:mid])
        right = separator_elem(list_[mid:])
        
        return merge(left, right)
    
    def merge(x, y):
        l, r = 0, 0
        tmp = []
        while True:
            if l >= len(x):
                tmp += y[r:]
                break
            elif r >= len(y):
                tmp += x[l:]
                break
            elif x[l] < y[r]:
                tmp.append(x[l])
                l += 1
            else:
                tmp.append(y[r])
                r += 1  
        return tmp
    
    if __name__ == "__main__":
        print(separator_elem([2, 4, 2, 5, 1, 9, 0]))
    # 输出：
    [0, 1, 2, 2, 4, 5, 9]

## 总结 ##

对于递归思想可以有如下总结：

*  采用递归编程最好持有“井底之蛙”的思想；
 *  递归的特点在于：它一次只打算解决一点点的问题。

对于递归实现可以关注两点：

*  递归的出口条件；
 *  归纳法中得到的规律。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70]: /images/20220402/2b2465c9f6cb4a4f8389f9ed09f57d56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU5MDUx_size_16_color_FFFFFF_t_70 1]: /images/20220402/d644ac1c7afd4fac9b9ba200b7ba13c5.png