如何写出你的第一个递归函数？

我们在学习一个新的东西时，常常使用现实中的东西作类比。学习编程也不例外。

但编程里面有一些术语或者思想或者理论，在现实中不容易找到类比的东西，此时初学者就很难理解了。

递归就是这样一个例子。现实生活中似乎找不到什么东西，能在自己的内部调用自己。

为了说明递归函数的调用过程，我们先从一个最简单的例子说起。

有一个列表，它是空列表，或者它里面有一个数字。再给你一个目标数。请写一个函数，判断目标数在不在这个列表中。不得使用 in关键字。

def check_in(checked_list, target):    """    checked_list是一个空的或者只有一个元素的列表，target是一个数字，判断这个数字是否在列表中    """    if not checked_list:        return False    if target == checked_list[0]:        return True    return False

这个逻辑非常简单，只要知道什么是列表就看得懂代码。

我们现在增加一点难度：

给定一个列表，它里面一定有两个数字，再给你一个目标数字，判断目标数字是否在这个列表中。不得使用 in关键字。

由于我们原来的函数check_in只能检查数字是否在一个只有一个元素的列表中，所以为了实现新的需求，就需要 再写一个新的函数。

我知道有同学跃跃欲试可能会这样写：

def check(checked_list, target):    for num in checked_list:        if num == target:            return True    return False

请先不要着急，因为本题不允许使用 in关键字。而且如果按你的写法，你就没有机会学会递归了。

我们尝试使用一个笨一点的办法，并且调用之前已经定义好的 check_in函数：

def check_in_2(checked_list, target):    """    注意，此时知道checked_list一定有两个数字    :param checked_list:    :param target:    :return:    """    part_1 = checked_list[0:1]    part_2 = checked_list[1:2]    if check_in(part_1, target) or check_in(part_2, target):        return True    return False

在这个函数里面，首先把 checked_list列表拆分为两个只包含一个元素的子列表 part_1和 part_2，然后把这两个子列表与目标数字分别传入 check_in函数。根据 check_in函数的返回来判断目标数字是否在原来的 checked_list中。只要目标数字在某一个子列表中，那么就一定在原来的总列表中。

现在再进一步，如果checked_list有且仅有三个数字怎么办呢？

这种情况下可以把三个元素的列表切分为两个元素的列表+一个元素的列表

def check_in_3(checked_list, target):    part_1 = checked_list[0:2]    part_2 = checked_list[2:]    if check_in_2(part_1, target) or check_in(part_2, target):        return True    return False

其中 part_1是一个包含两个数字的列表， part_2是一个包含一个数字的列表。

同理，当 checked_list有4个元素的时候，其实可以切分为两个各有两个元素的列表。从而分别调用两次 check_in_2；当 checked_list有5个元素的时候，可以切分为一个有三个元素的列表和一个有两个元素的列表，从而分别调用 check_in_3和 check_in_2。

此时，大家有没有注意到一个现象——

• 函数 check_in_2是通过调用 check_in来实现的。
• check_in_3是通过调用 check_in_2 和 check_in来实现的。
• check_in_4是通过调用 check_in_2来实现的。
• check_in_5是通过调用 check_in_3和 check_in_2来实现的。
• ……

所以，对于 check_in_n，其中n是任意一个大于1的数字，归根到底，它都是通过多次调用 check_in来实现的。

那么问题来了，我要检查的列表里面有100个元素，我应该怎么办呢？

难道我要写一个 check_in_100？那么是不是我还要再写一个 check_in_50？那是不是还要再写一个 check_in_25、 check_in_13、 check_in_12？

这样写起来太麻烦了。我怎么知道你传给我的列表里面有多少给元素？难道为了处理所有的情况，我需要针对每一个元素个数的列表都单独函数来处理？

既然所有的情况归根到底都是调用 check_in函数，那能不能只定义这一个函数，不再额外定义其他函数？

为了理解这个问题，大家注意观察，无论是 check_in_2、 check_in_3还是 check_in_4，他们的函数写的格式都是一样的：

def check_in_n(checked_list, target):    part_1 = checked_list[0:x]    part_2 = checked_list[x:]    if check_in_x(part_1, target) or check_in_y(part_2, target):        return True    return False

只不过具体调用的函数名不一样。

现在，准备两台装了Python的电脑，在你的电脑上，你定义一个函数：

def check_in(checked_list, target):    """    checked_list一定是一个有两个元素的列表    """    if checked_list[0] == target or checked_list[1] == target:        return Truereturn False

在我的电脑上，我也定义一个函数：

def check_in(checked_list, target):    """    checked_list一定是一个有三个元素的列表    """    if checked_list[0] == target or checked_list[1] == target or checked_list[2] == target:        return Truereturn False

这个时候，我手上有一个5个元素的列表：[1,2,3,4,5]和目标数字4。

首先，我对你隔空喊话：

我：我现在给你一个列表 [1,2]和目标数字4，你用你的函数帮我跑一下，看看返回的是True还是False 你：返回的是False

然后，我把列表 [3,4,5]和目标数字4放入我自己的函数里面再跑一次，发现返回的是True。

所以我得出了结论：数字4在列表[1, 2, 3, 4, 5]中。

请大家注意，在这个过程中，涉及到了两个函数，他们的名字都叫做 check_in。但是他们的代码不一样。

好了，刚才我们涉及到了两个概念：

1. 不同的函数，他们里面的代码结构可以一模一样。
2. 名字相同的函数，他们可以不一样（例如运行在两台不同的电脑上）。

如果把这两个概念放在一起，会发生什么呢？

回到刚才检查数字是否在列表中的例子，我们现在把所有的函数全部合并到 check_in里面去:

def check_in(checked_list, target):    if not checked_list:        return False    if len(checked_list) == 1:        if checked_list[0] == target:            return True        return False    mid = len(checked_list) // 2    part_1 = checked_list[:mid]    part_2 = checked_list[mid:]    result = check_in(part_1, target) or check_in(part_2, target)    return result

从下图的测试结果可以看出，这样写是没有问题的：

不论传入的checked_list里面有多少个元素，我们总是可以把它对半分开得到两个子列表；子列表的长度就减少了一半。把子列表再对半分开，长度又减少了一半。不停地分割，最终就会变成非常多的包含1个或者0个元素的列表，从而直接返回True或者False。

图中8，9，10行就是把原来的列表对半分开的过程。

可能大家比较费解的也就是第11行了。

在函数里面调用函数自己的时候，请大家回想我举的那个隔空喊话的例子。

对于被调用的check_in来说，它完全不需要关心是谁调用的它。它只需要知道传进来两个参数，一个是checked_list列表，一个是target整数。如果checked_list里面的元素是0个或者1个，那么就根据逻辑返回True活着False。如果超过1个，那么就对半分，然后把两个子列表“隔空喊话”传给另一个名字也叫做 check_in的函数。

简单来说，递归的时候，函数不需要关心是谁调用的它的。它只需要知道传进来的参数是什么，怎么处理。当它要在自己内部调用另一个 check_in的时候，它仅仅是把这当做是一个和自己名字一样的函数而已，它不需要知道这个被自己调用的，和自己名字一样的函数里面是什么逻辑。

理解了调用关系，那么另一个问题又来了，当递归的时候，剩下的没有运行的代码，他们在干嘛，已经运行的代码，他们生成的变量值哪去了？

想象这样一个场景：

你正在看书，刚刚看了3页，突然电话响了，你放下书，去接听电话，电话打到一半，家里的水管爆了。你放下电话，去关闭了水闸，回来拿起电话继续讲。电话打完以后，回去继续看书。

这里面，当你关了水闸回来继续打电话的时候，你是接着上次没有说话的话继续说的，不需要和对方从头开始。当你打完电话会去看书的时候，你是从上次断掉的地方继续看，不需要从第1页开始看。

这是因为，当你要去接电话的时候，你脑子会记住你刚刚看到了哪里。当你放下电话去关水闸的时候，你的脑子也会记住你刚才电话讲到了哪里。

在递归的时候，也是这样一个流程。函数调用自己的一瞬间，系统会自动保存当前的各种数据，然后进入被调用的函数里面。在里面如果还要调用一次自己，那么就继续保存一次当前的数据。注意两次保存是有先后顺序的。先保存的数据后读取，后保存的数据先读取（也就是传说中的栈）。最里面的事情做完以后，返回上一层，系统把刚才保存的数据拿出来，继续操作，操作完成以后，再返回上上层，再继续操作……

保存数据的栈是有大小的，所以当你无限制地递归调用自身时，就会报错。因为栈满了，新的数据没有办法保存了。

最后，可能有人会吐槽我这篇文章举的那个检查目标数字是否在列表中的代码写的太麻烦了，可以用一个for循环就搞定的事情，非要上递归，简单问题复杂化。

那么这个问题我们加一个限制条件：列表中的数字是升序排列的。

此时，如果使用for循环，时间复杂度为O(n)。

如果用递归的话，可以通过二分查询，把时间复杂度降为：O(logn)。

在后面的文章中，我们将会讲到，如何使用递归实现二分查找和遍历二叉树。

PS：感谢产品经理在这篇文章撰写过程中提供的帮助。