谷歌面试问题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)
还是没太明白？加个图：只有一个门，后进先出来。计算机得记得它先后要干活的具体顺序。

文章插图
嵌套算法
基本执行看明白了，一个基本例子理解一下：

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

特点：

总结的函数式就是递归自己调用自己的写法:F = n*f(n-1)
父亲使用儿子的返回结果

文章插图
求n的阶乘
运行结果：
In stack:3
In stack:2
out stack:2 -人工添加
out stack:3 - 人工添加
6
总结：
嵌套算法的特点：
• 每次有不同的输入
• 但是每次运算相同
• 必须有停止嵌套的条件（防止死循环）
• 与循环的不同：每次输入数据范围缩小
为什么要用嵌套算法：
• 能用嵌套不用循环：好写好读，-- 这条可以有异议
• 问题可以分解为相同的小问题（处理的数据范围变小）
• 广泛应用于树，图数据结构中
• 比如：树的深度优先搜索，如果你发现一个问题可以通过搜索来解决，那么你就有一个很好的递归算法候选。