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

2024-01-10 10:04:09 职场攻略 投稿:一盘搜百科
摘要你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准

你对递归很纠结吗?

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

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

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

 

算法题中超过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

总结:

嵌套算法的特点:

• 每次有不同的输入

• 但是每次运算相同

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

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

为什么要用嵌套算法:

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

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

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

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

 

声明:一盘搜百科所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系 88888@qq.com