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

作者: | 更新日期:

递归,很多人都学不会的基础,我尝试讲解一下。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/pN9T9hyjClHFNfajxlWKkA

一、背景

之前已经分享了很多算法,如数组、字符串、链表、二叉树、搜索树、二分查找等等,大家可以在公众号历史记录里找到。
周末我也会抽个时间整理一下公众号的菜单,供大家快速找到入口。

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

二、递归原理

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

也许你会有疑问,怎么能通过调用自己解决问题呢?
这个黑科技的关键在于,递归每次调用自身的时候,调用的函数只需要解决一个子问题。
通过不断的递归调用,问题不断的变小,直到最后不需要递归就可以解决。

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

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

当然,函数最终需要有明确的功能与定义。
函数的功能是啥明确了,我们才能确定如何定义参数,如何定义返回值。

下面看两个例子吧。

三、翻转字符串

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

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

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

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

最后来看函数出口。
实际上根据子问题的拆分特征,出口很容易确定。
数组长度每次减2,那小于2时,就不需要拆分了,直接得到答案(什么都不需要做)。

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

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

题意:给一个链表,两两交换链表的相邻节点。
要求:不能修改节点的值,只能修改指针的值。

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

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

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

这里会遇到一个问题:当前的两个节点第二个会调整到第一个,第一个会调整到第二个。那第二个怎么知道指向后面链表的哪一个呢?
一种简单的思路是:链表翻转后返回值就是当前链表的头。这样,调整后第二个节点直接指向子问题的返回值即可。
这样,子问题的实现就比较简单了,

接下来就是出口,根据子问题可以发现,子问题要求链表节点至少有两个。
所以对于空链表和只有一个节点的链表,是不能拆分子问题的。
空链表就继续返回空链表,只有一个节点的链表就返回链表自身。

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

五、最后

对于递归,已经写过程序的人都会感觉这个很简单。
但是如果看过语法解析或者协议解析的代码,比如json库、protobuf库,就会发现这些库也就是一些递归函数的互相调用。

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

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/pN9T9hyjClHFNfajxlWKkA

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越