Python | 一路递归深似海

问题描述

不知道小伙伴们在写代码时有没有遇到这种情况：每次写递归就莫名其妙地写出来了，没运行之前自己完全不知道对不对，就是写递归完全靠直觉。又或者一路递归深似海，从此回不来……，接下来让我们好好研究研究递归这个磨人的小妖精到底是怎样的。

解决方案

百度百科上对递归算法的定义如下：递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。相信很多小伙伴看了之后一脸懵逼，没关系，接下来我们用画图举例的方式来理解什么是递归。假如我们求一个列表 [1,3,5,7,9] 中所有数字的和，在不使用for和while的情况下来解决这个问题(为了方便举例给出的数据规模较小，实际上列表求和的数据是不确定有多少的)。我们认识到列表求和并不是把数据一块全加在一起一块算，它最终是由一次次的加法实现的，而加法恰有两个操作数，这个是确定的。因此我们可以把这个列表求和问题分解为规模更小且固定的两个数求和。为了实现问题规模的分解，我们换一个角度来看这个问题，将其写成下面这种表达式：(1+(3+(5+(7+9))))。对于这个式子，最内层的括号(7+9),这是无需循环就可以计算的，实际上整个求和过程如下：

观察上述过程的重复模式，列表求和实际上是这样的：列表的和 = 首个数 + 余下列表，如果列表所包含的数少到只有一个的话，它的和就是这个数。将这个算法转化为代码我们可以这样做：先定义一个函数sum，其参数为numList。首先判断numList长度是否为1，如果是1直接返回numList[0]；否则返回numList[0] + 余下的数的和，余下的数的和我们知道是numList[1:]，我们将这个更短的列表作为函数sum的参数传进去。图解如下：

结语

以上就是对递归算法的简单讲解，总体来说需要注意递归算法需要注意以下三点：1.必须要有结束条件，否则将会一路递归深似海，从此回不来；2.能减小问题规模，否则递归算法就没意义了；3.必须调用自身，解决减小了规模的相同问题。下次我们将用递归算法解决汉罗塔问题。

实习编辑：李欣容

稿件来源：深度学习与文旅应用实验室（DLETA）