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

栏目: 数据库 · 发布时间: 3年前

内容简介:之前已经分享了很多算法,如数组、字符串、链表、二叉树、搜索树、二分查找等等,大家可以在公众号历史记录里找到。周末我也会抽个时间整理一下公众号的菜单,供大家快速找到入口。今天大家已经有一定的算法思维、逻辑思维了,我们再回头来看看最基础的递归是什么吧。

一、背景

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

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

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

二、递归原理

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

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

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

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

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

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

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

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

下面看两个例子吧。

三、翻转字符串

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

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

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

然后看子问题。

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

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

最后来看函数出口。

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

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

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

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

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

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

要求:不能修改节点的值,只能修改指针的值。

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

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

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

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

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

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

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

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

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

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

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

五、最后

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

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

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

-EOF-


以上所述就是小编给大家介绍的《递归就是这么简单(原理篇)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

JavaScript核心技术

JavaScript核心技术

Shelley Powers / 苏敬凯 / 机械工业出版社 / 2007-6 / 45.00

Ajax是当今Web开发领域最流行的词汇。而JavaScript与CSS、XML和DOM几种老技术,加上XMLHttpRequest就构成了Ajax的四大基石。对于JavaScript,一些更资深的同事告诉我的感觉是失望。面对不同的浏览器和浏览器的不同版本,没有优秀的调试开发工具,JavaScript成了软件开发的泥潭。. 而本书的出版则给我们增加了一丝解决这些问题的信心。 它从最简单......一起来看看 《JavaScript核心技术》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

SHA 加密
SHA 加密

SHA 加密工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具