V
主页
【递归】什么是递归?
发布人
要理解递归、首先 要理解递归 递归就像我们查字典的时候 当查找一个词时,发现它的解释中某个词仍然不懂,于是开始查这第二个词 像千钧一发这个词的解释中 千钧一词仍然不懂 于是开始查找千钧的意思 在千钧的解释中 一石为四钧 一石这个词还是不懂 于是继续查找 一石 到这里我们明白了 一石指的是120斤 就像这样我们一直查找,直到有一个词的解释完全明白为止 那么我们就可以开始后退 一石指120斤,那么4钧为1石,则1钧为30斤 则千钧为3万斤 到此我们就彻底明白了千钧一发的意思 递归 递归,先有递再有归 递的意思就是将问题拆解成子问题来解决 子问题再拆解为子问题,直到被拆解的问题无需再拆解为更细的子问题时 就像在字典中一直查找不明白的词语 的情况 归的意思是 最小的子问题得到解决了,那么它的上一层也会有由于它的解决而被解决,上一层的子问题解决了,那么上上层的问题自然也就解决了,一直到开始的问题被解决 在编程中 递归简单来说,就是如果在函数中存在着调用函数本身的情况,这种就可以称为递归 我们以一个阶乘函数的实现为例 可以看到在 factorial 函数中,存在着一个 factorial 函数的调用,所以这个函数就是递归函数 factorial 函数我们简写下,改为f 我们以阶层f 6 为例,看下它的递和归 求解问题f 6,n为6,n大于1 则return n * f n-1,当前n为6,则 f6 = 6 * f5 所以 f 6 被拆解为 f 5 的子问题 同理 f 5 = 5 * f 4 也需要进一步拆解 f 4 = 4 * f 3 f 3 = 3 * f 2 f 2 = 2 * f 1 当n等于1时f 1 = 1 到这时 f 1 的问题解决了,无法继续往下递了 进行归 既然f1解决了,那么 f 2 只依赖于f1 所以f2问题也可以解决了 f 3 依赖 f 2的结果,f2解决了那么f3也可以解决了 同理 f4、f5、f6都可以解决 所以递归的本质就是把问题拆分成具有相同解决思路的子问题 直到最后被拆解的子问题再也不能拆分 解决了最小粒度可求解的子问题后,在归的过程中自然而然地就解决了最开始的问题 我们在看个稍微进阶点的 青蛙跳台阶的问题 一只青蛙可以一次跳1级台阶或者一次跳2级台阶 跳上第1级台阶只有1种跳法 直接跳1级即可 跳上第2级台阶有两种跳法 每次跳1级,跳两次 或者1次就跳两级 问 要跳上第n级台阶有多少种跳法呢? 仔细看题目,一只青蛙一次只能跳1级或者2级台阶 自上而下的思考,也就是说如果要跳到n级台阶只能从 n-1 或 n-2级开始跳 所以问题就转化为跳上 n-1 和n-2级台阶的跳法了 如果f n 代表跳到n级台阶的跳法 那么从以上分析可得 f n的函数为 f(n) = f(n -1) + f(n -2) 显然这就是我们要找的问题和子问题的关系 而显然当 n = 1和n = 2时,即跳到1 2 阶台阶时是问题的最终解,也是已知解 n=1时有一种跳法,n=2时有两种跳法 那么跳到第6层时有多少种跳法 可以看作求解问题 f 6 n = 6时 返回 f 5 + f4 那么 f6被拆解为 f5 和 f4 的子问题 继续 递 下去,求解 f5 则需要知道 f4和f3 求解 f4 需要知道 f3 和 f2 求解 f 3 需要知道 f2 和 f1 f2已知等于2 f1已知等于1 问题已经得到最小化,无法继续递下去了 进行归操作 f3 = f 2 + f 1,f2有2种跳法f1有1种,所以 f3 = 2 + 1 = 3 f4=f3+f2,f3有3种,f2有2种 所以f4有5种跳法 f5=f4+f3,f4有5种,f3有3种 所以f5有8种跳法 f6=f5+f4,f5有8种,f4有5种 所以f6有13种 也就是说青蛙跳上第6阶有13种不同跳法 写递归代码的关键就是找到如何将大问题分解为小问题的规律 然后再推敲终止条件
打开封面
下载高清视频
观看高清视频
视频下载器
十分钟学会编程的本质【收藏级】
Qt 这么强大为什么火不起来?
【neko算法课】递归与递推【2期】
『教程』堆栈是个啥?
看到递归就晕?带你理解递归的本质!
热血编程 (第五集)| 双指针的巧妙转换
回溯七步法,从此回溯是送分题。蓝桥杯国赛真题,路径之谜,真·动画教编程,适合语言初学者或编程新人。
栈 溢 出
什么是递归?
他居然做出了Leetcode第一题!【Leetcode1. 两数之和】
【算法】递归真的不好用
你知道循环、迭代、递归的区别吗
程序员的封神之作
【C语言】递归就是栈思想的应用
雷军20多年前写的代码,你见过吗?
也是终于学会怎么写Hello World了
print("a")需要多长时间?
每次写递归都要靠直觉? 这次带你学透二叉树的递归遍历!| LeetCode:144.前序遍历,145.后序遍历,94.中序遍历
【程序员吐槽会】只有程序员才能听懂的梗
算法20天速通!leetcodeHot100-- 贪心算法,启动!
【有挂!!】二叉树遍历秒解,前序遍历、中序遍历、后序遍历
【C语言】用递归解决汉诺塔问题太容易不过了
Linux入门扫盲:Shell是什么
有个说法:“「递归」是检验编程天赋的试金石”;而本视频打破天赋壁垒,助你快速掌握递归。
辞退公司骨干,结果全员辞职
废物大学生自研IDE
【科普】递归反人类?
会写递归超越了多少程序员?
你真的懂动态规划么?力扣 No.741 摘樱桃,真·动画教编程,适合语言初学者或编程新人。
遇到递归还会晕?通过函数调用栈的方式,理解递归函数执行过程,彻底解决递归眩晕
递归算法 【超详细】
小白才会重构代码屎山,大佬都是。。。
哈夫曼树和哈夫曼编码, 看完秒懂!
十分钟带你学会递归算法!
python迷惑行为:我继承我自己
什么是树?动画解析,数据结构与算法合集
【动画演示】链表详解及其底层机制 C语言
自学C语言的最怖的地方是什么?
【史上最燃算法刷题】双指针YYDS || Leetcode11. 盛水最多的容器
分而治之:编程算法背后的哲学智慧