递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自己的爬坑经历了

记得在第一次碰见递归是在学C语言的时候,当时讲解递归这种编程思想用了一个例子:求n!

由于C语言很久不用代码格式已经忘记=_=!因此这里用python重写一遍这个函数:

def f(n):
    if n == 1:
        return 1
    return n * f(n-1)

不得不说这是一个非常简单的例子来讲解递归函数:一个函数在内部调用其自身。这种调用很很巧妙得避免了利用for循环来求解n的阶乘这个问题因此让当时身为初学者的我也能感受到递归函数的强大。

但这个例子看起来容易,但递归实际操作起来却有一定难度。尤其是让自己写一个稍微复杂点的递归时,发现自己逻辑就混乱不清。自己其实也经历过这样一个过程,开始的时候死活无法理解,后来网上搜了搜如何理解递归。在知乎看到两种解释自己十分受用,自己现在能成功解决一个递归问题也是得益于这两种思想:

1.递归其实与数学归纳法有类似之处。数学归纳法是怎么处理问题的呢?首先我们证明在初始情况(一般也是n=1)是成立的,然后假设当n=k时成立,由n=k成立推导出n=k+1时成立。这个过程应该是感到非常熟悉,操作起来也是犹如行云流水了。那么递归呢?非常类似,首先我们要列出相对于数学归纳法里初始情况(n=1)时函数的返回值,这相当于递归函数碰到的特殊情况(求n!时,当n=1可以看做是一种特殊情况)。列出特殊情况后,在写出普遍情况下函数如何执行(也就是n != 1时的情况),这时我们就要推导n = k和n=k-1的关系了,因为我们在执行n=k时需要用到n=k-1时的结果。这时又要用到第二个思想。

2.在写一个递归函数时,可以将递归函数看做一个黑匣子(黑匣子就是我们不管也不知道其中细节,也不理解是怎么实现的,总之就是能实现功能的)。它可以接收一个输入并给出想要的输出,注意,此时要有自信,相信自己写的这个函数可以完成预期的功能。如果这么想,当把n=k-1输入这个函数时,输出的自然就是当n=k-1时我们想要得到的输出,此时我们要相信这个输出是已经解决了n=k-1这种情况的。那么省下的步骤就是在n=k是调用n=k-1时函数输出的结果了,也就是上一个思想中的推导n=k时的输出对n=k-1时的输出的依赖关系了。

上面两种思想:一种是将递归看成数学归纳法的实现过程,另一种是将递归看成一个黑匣子。如果是完成一个递归思想编程任务应该可以完成了。但是这样还是不够的:我们不能总是面对一个自己写的黑匣子吧?

如何搞清楚这个黑匣子的内部结构呢?

建议自己对着一个比较复杂的递归函数(自己当时是花了一个下午的时间看着leetcode上Binary Watch的递归解决方法来理解的),一步一步不嫌麻烦得画出这个函数是如何实现自我调用的,也就是将函数自我调用的栈画出来。就会探知黑匣子内部其实是一环扣一环的关系,就像数学归纳法由一步推出下一步。自己实现一到两次就会对消除的黑匣子的恐惧。

最后自己按照上面的两个思想实现一个递归函数,自己实现了一次后有了信心后面再碰到就得心应手了,理解起来也更加轻松。

:)最后祝大家爬坑愉快

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏take time, save time

你所能用到的数据结构(二)

      周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,...

3126
来自专栏落影的专栏

程序员进阶之算法练习(二十八)

前言 四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 ...

4589
来自专栏程序员互动联盟

【答疑解惑第三十八讲】初学者做项目需要掌握哪些东西?

疑惑一 【答疑解惑】初学必须掌握的数据结构有哪些? 数据结构有很多,难以程度也不相同,初学者应该掌握哪些基本的数据结构呢?作为一个过来人,我觉得作为一个初学者应...

3558
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3765
来自专栏编程

编程老司机带你玩转C语言指针

很多初学编程的小伙伴都会选择C语言作为第一门学习的编程语言,应为C语言作为一门底层语言相对于其他的高层语言来说更加容易学习。可以来帮助正在学习编程的小伙伴更加快...

2266
来自专栏张俊红

Python面向对象编程

2045
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

2967
来自专栏CDA数据分析师

就算不做数据分析师也要学会这8个IF函数

今天所讲的IF函数,包括excel中含有IF的系列函数,共有8个,每个函数列举最了常用的2~3个公式,希望能对同学们有用。 一、IF函数 作用:根据条件进行判断...

2066
来自专栏数据库

用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题 场景: A集合有8个元素:ali、boy、c、dog、e、f、g、h, B集合有5个元素:boy、c、dog、e、h 问B中...

1999
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

4354

扫码关注云+社区