递归就是这么简单(原理篇)

一、背景

之前已经分享了很多算法，如数组、字符串、链表、二叉树、搜索树、二分查找等等，大家可以在公众号历史记录里找到。

周末我也会抽个时间整理一下公众号的菜单，供大家快速找到入口。

今天大家已经有一定的算法思维、逻辑思维了，我们再回头来看看最基础的递归是什么吧。

二、递归原理

定义：递归是函数通过调用自身这个函数来解决问题的一种方法。

也许你会有疑问，怎么能通过调用自己解决问题呢？

这个黑科技的关键在于，递归每次调用自身的时候，调用的函数只需要解决一个子问题。

通过不断的递归调用，问题不断的变小，直到最后不需要递归就可以解决。

另外，为了防止陷入死循环，递归需要满足两个性质才行。

1. 出口，不需要继续递归就可以直接结束函数。
2. 一系列规则，用于拆分问题，最终会导向出口。

当然，函数最终需要有明确的功能与定义。

函数的功能是啥明确了，我们才能确定如何定义参数，如何定义返回值。

下面看两个例子吧。

三、翻转字符串

题意：给一个字符串数组，求使用 O(1) 的空间复杂度递归翻转原数组。

思路：这里的目的是练习递归，所以需要做的事情有三个，分别是函数定义、拆分子问题、函数出口。

首先是明确函数定义：翻转给定的数组。

然后看子问题。

每次我们可以将第一个和最后一个元素交换位置，然后子问题就转化为了长度减 2 的数组。

这样子问题就完成拆分了。

最后来看函数出口。

实际上根据子问题的拆分特征，出口很容易确定。

数组长度每次减 2 ，那小于 2 时，就不需要拆分了，直接得到答案（什么都不需要做）。

由此，这道题的递归代码我们就可以写出来了。

四、两两交换链表相邻节点

题意：给一个链表，两两交换链表的相邻节点。

要求：不能修改节点的值，只能修改指针的值。

思路：依旧是按函数定义、拆分子问题、函数出口三步来分析问题。

函数定义：对输入的链表两两进行翻转。

拆分子问题：先对链表前两个翻转，然后链表后面的递归处理即可。

这里会遇到一个问题：当前的两个节点第二个会调整到第一个，第一个会调整到第二个。那第二个怎么知道指向后面链表的哪一个呢？

一种简单的思路是：链表翻转后返回值就是当前链表的头。这样，调整后第二个节点直接指向子问题的返回值即可。

这样，子问题的实现就比较简单了，

接下来就是出口，根据子问题可以发现，子问题要求链表节点至少有两个。

所以对于空链表和只有一个节点的链表，是不能拆分子问题的。

空链表就继续返回空链表，只有一个节点的链表就返回链表自身。

这样，两两翻转链表的代码就出炉了。

五、最后

对于递归，已经写过程序的人都会感觉这个很简单。

但是如果看过语法解析或者协议解析的代码，比如json库、protobuf库，就会发现这些库也就是一些递归函数的互相调用。

那为什么说起递归会感觉简单，实现一个json库或者程序语言的语法分析很多人认为很难呢？

-EOF-