您当前的位置:首页 > 生活百科 > 职场

谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

时间:2020-06-21 22:30:24  来源:  作者:

你对递归很纠结吗?

虽然代码量少,理解起来太费劲?如果你这么想那就对了。

因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。

可是程序员面试不得不准备算法题,尤其是竞争激烈的公司,不管你进去拧不拧螺丝钉。

 

算法题中超过50%的问题直接或间接的与递归相关。

重要事情说三遍,因为这很重要

 

今天我们就掰开它看看,到底有多难。

玩过俄罗斯套娃么?一层一层的套,里面有更小的娃娃。

如果中间某个娃娃里面放了一枚钻戒,让你去找出来—这就是嵌套问题的一种。

 

谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

俄罗斯套娃

听过马三立的《祖传秘方》单口相声么?治疗浑身发痒的神器-纸条包纸条(答案是:挠挠)

实际上,答案不一定在最后一张纸条里面,哪张都可能,哈哈。没看过的自己补一下。

谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

单口相声-祖传秘方

开心完了看看理解递归的的关键是啥:

  • 输出并不总是按照它在代码中出现的顺序出现。最重要的是按照编译器的方式遍历代码。
  • 按照代码顺序前后关系理解输出,你就完蛋了。

例子说话:

就走一遍啥也没干是啥样?

谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

嵌套Stack

执行结果看下面:全都入栈,再从孩子的孩子最底层执行出来。

in stack for recurser_print(5) output not trigger yet

in stack for recurser_print(4) output not trigger yet

in stack for recurser_print(3) output not trigger yet

in stack for recurser_print(2) output not trigger yet

in stack for recurser_print(1) output not trigger yet

exit and print n for recurser_print(1)

exit and print n for recurser_print(2)

exit and print n for recurser_print(3)

exit and print n for recurser_print(4)

exit and print n for recurser_print(5)

还是没太明白?加个图:只有一个门,后进先出来。计算机得记得它先后要干活的具体顺序。

谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

嵌套算法

基本执行看明白了,一个基本例子理解一下:

  • 例子:求n的阶乘
  • 如果n=5 那么 数学计算方法: result = 5 * (5-1) * (5-2) * (5-3) * (5-4)也就是 5*(4*(3*(2*(1))))

特点:

  • 总结的函数式就是递归自己调用自己的写法:F = n*f(n-1)
  • 父亲使用儿子的返回结果
谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?

求n的阶乘

运行结果:

In stack:3

In stack:2

out stack:2 -人工添加

out stack:3 - 人工添加

6

总结:

嵌套算法的特点:

• 每次有不同的输入

• 但是每次运算相同

• 必须有停止嵌套的条件(防止死循环)

• 与循环的不同:每次输入数据范围缩小

为什么要用嵌套算法:

• 能用嵌套不用循环:好写 好读,-- 这条可以有异议

• 问题可以分解为相同的小问题(处理的数据范围变小)

• 广泛应用于 树, 图 数据结构中

• 比如: 树的深度优先搜索,如果你发现一个问题可以通过搜索来解决,那么你就有一个很好的递归算法候选。

 



Tags:谷歌面试问题50%需要用递归   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21  Tags: 谷歌面试问题50%需要用递归  点击:(116)  评论:(0)  加入收藏
▌简易百科推荐
毕业后不重视自己的档案,等到考研、考编、考公务员、单位入职等需要用到档案时,才想起来查询自己的档案。但是,很多人查询档案没有经验,不知道该从何查起。下面给大家介绍查询个...【详细内容】
2021-12-23  帮帮团人力资源    Tags:个人档案   点击:(14)  评论:(0)  加入收藏
评职称可谓是工程人事业发展中的一件大事了,可以说一般想要在行业中持续地、更好地发展的人都会选择评个中级职称! 怎么评广东省建筑中级职称? 在评审时工程业绩最为重要。那...【详细内容】
2021-12-23  资深职称老师—小丽    Tags:职称   点击:(4)  评论:(0)  加入收藏
职场中,事情做得漂亮,不一定结局漂亮;但是善于谋人,把人打通了,出手一般就是巅峰。人情社会尤其如此,说到底工作是人定的,好不好也是人说的,有人为你说话,你就是能力强。没人看到你,工...【详细内容】
2021-12-22  胖子说职场经验    Tags:职场   点击:(4)  评论:(0)  加入收藏
一、在国企,能改变命运的只有你自己。你想改变,就总有办法。你认命,就不要埋怨命运不公。多少领导一样是从基层爬上去的。也许你会说,他们背后有人。我也不反对,但总有那么20%左...【详细内容】
2021-12-21  职场真谛    Tags:国企   点击:(6)  评论:(0)  加入收藏
又到年底了,有更好的工作选择?想跳槽?社保咋处理?以及社保需要注意的小问题是什么?一文全理清!一、打工人离职手册之社保全指南 二、需要注意的社保小问题 ...【详细内容】
2021-12-17  恒企会计网校    Tags:离职指南   点击:(6)  评论:(0)  加入收藏
在个案辅导中,也经常遇到公务员面试前的准备和辅导。首先,我其实挺想吐槽公考的笔试和考试机制的,让我先一吐为快。公务员考察的面非常多,从表达能力这种表面的,到价值观这种底层...【详细内容】
2021-12-14  为好优姐姐    Tags:公务员面试   点击:(12)  评论:(0)  加入收藏
公务员面试形式进行了创新,增加了结构化小组面试这一形式,在结构化的基础上增加了考试互评和回应的环节,这一改变增加了考试难度,也给许多考试造成了困惑,那今天就结构化小组的点...【详细内容】
2021-12-14  红河华图教育    Tags:公务员面试   点击:(14)  评论:(0)  加入收藏
在各级党政机构之中,我们经常会听到一个称呼——“常务副职”,例如县政府有常务副县长,组织部有常务副部长等等。其实,常务副职只是一个约定俗成的简称,其准确名称叫做...【详细内容】
2021-12-14  瑛杰小猪  今日头条  Tags:常务副职   点击:(19)  评论:(0)  加入收藏
在职场,什么都可以没有,就是不能没有情商。没有情商的人,在职场注定难成大器。人际关系搞不定,说话口无遮拦,为人处世更是不够圆滑,处处受限,处处是破绽。尤其是和领导相处,连对方的...【详细内容】
2021-12-14  第一桶金学派    Tags:领导   点击:(8)  评论:(0)  加入收藏
在职场,除了个人的工作能力以外,还要学会去不断的积累自己的人际关系。因为有了关系,就有了渠道,有了机会,有了方法,有了财富……越是和厉害的人交往,你自己也会变得越...【详细内容】
2021-12-10  第一桶金学派    Tags:职场   点击:(12)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条