谷歌面试问题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

总结：

嵌套算法的特点：

• 每次有不同的输入

• 但是每次运算相同

• 必须有停止嵌套的条件（防止死循环）

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

为什么要用嵌套算法：

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

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

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

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