程序员必备的基本算法:递归详解
前言递归是一种非常重要的算法思想 , 无论你是前端开发 , 还是后端开发 , 都需要掌握它 。 在日常工作中 , 统计文件夹大小 , 解析xml文件等等 , 都需要用到递归算法 。 它太基础太重要了 , 这也是为什么面试的时候 , 面试官经常让我们手写递归算法 。 本文呢 , 将跟大家一起学习递归算法~
- 什么是递归?
- 递归的特点
- 递归与栈的关系
- 递归应用场景
- 递归解题思路
- leetcode案例分析
- 递归可能存在的问题以及解决方案
?
递归最恰当的比喻 , 就是查词典 。 我们使用的词典 , 本身就是递归 , 为了解释一个词 , 需要使用更多的词 。 当你查一个词 , 发现这个词的解释中某个词仍然不懂 , 于是你开始查这第二个词 , 可惜 , 第二个词里仍然有不懂的词 , 于是查第三个词 , 这样查下去 , 直到有一个词的解释是你完全能看懂的 , 那么递归走到了尽头 , 然后你开始后退 , 逐个明白之前查过的每一个词 , 最终 , 你明白了最开始那个词的意思 。
?
来试试水 , 看一个递归的代码例子吧 , 如下:
public int sum(int n) {if (n <= 1) {return 1;}return sum(n - 1) + n; }
递归的特点实际上 , 递归有两个显著的特征,终止条件和自身调用:- 自身调用:原问题可以分解为子问题 , 子问题和原问题的求解方法是一致的 , 即都是调用自身的同一个函数 。
- 终止条件:递归必须有一个终止的条件 , 即不能无限循环地调用本身 。
文章插图
递归与栈的关系其实 , 递归的过程 , 可以理解为出入栈的过程的 , 这个比喻呢 , 只是为了方便读者朋友更好理解递归哈 。 以上代码例子计算sum(n=3)的出入栈图如下:
文章插图
为了更容易理解一些 , 我们来看一下 函数sum(n=5)的递归执行过程 , 如下:
文章插图
- 计算sum(5)时 , 先sum(5)入栈 , 然后原问题sum(5)拆分为子问题sum(4) , 再入栈 , 直到终止条件sum(n=1)=1 , 就开始出栈 。
- sum(1)出栈后 , sum(2)开始出栈 , 接着sum(3) 。
- 最后呢,sum(1)就是后进先出 , sum(5)是先进后出 , 因此递归过程可以理解为栈出入过程啦~
- 阶乘问题
- 二叉树深度
- 汉诺塔问题
- 斐波那契数列
- 快速排序、归并排序(分治算法也使用递归实现)
- 遍历文件 , 解析xml文件
- 第一步 , 定义函数功能
- 第二步 , 寻找递归终止条件
- 第二步 , 递推函数的等价关系式
1.定义函数功能定义函数功能 , 就是说 , 你这个函数是干嘛的 , 做什么事情 , 换句话说 , 你要知道递归原问题是什么呀?比如你需要解决阶乘问题 , 定义的函数功能就是n的阶乘 , 如下:
推荐阅读
- 程序员为教师妻子开发应用:将iPhone变成文档摄像头
- 荣耀V40正式得到确认!参数配置也基本确定!售价或将是惊喜
- 九千元买的手机,最基本的功能都不好用,男子:还能干什么?
- 悔哭!一程序员误把7500个比特币当垃圾扔掉,估算约2.4亿美元
- 2.4亿美元打水漂!程序员小哥把7500个比特币当垃圾扔掉 硬盘找不回
- 程序员开发抢茅台脚本:2天就刷榜Github
- 为什么我喜欢C语言,却非常讨厌C++?一位国外程序员的回答
- 程序员怎么保护头发?雷军回应
- NVIDIA Broadcast体验 主播必备30系显卡
- 北美程序员Tinder翻车实录