你对递归很纠结吗?
虽然代码量少,理解起来太费劲?如果你这么想那就对了。
因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。
可是程序员面试不得不准备算法题,尤其是竞争激烈的公司,不管你进去拧不拧螺丝钉。
算法题中超过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
总结:
嵌套算法的特点:
• 每次有不同的输入
• 但是每次运算相同
• 必须有停止嵌套的条件(防止死循环)
• 与循环的不同:每次输入数据范围缩小
为什么要用嵌套算法:
• 能用嵌套不用循环:好写 好读,-- 这条可以有异议
• 问题可以分解为相同的小问题(处理的数据范围变小)
• 广泛应用于 树, 图 数据结构中
• 比如: 树的深度优先搜索,如果你发现一个问题可以通过搜索来解决,那么你就有一个很好的递归算法候选。