递归算法大家应该都不陌生吧，其实最开始遇见递归应该是在数学课上，类似于 f(x)=f(x-1)+f(x+1)，f(1)=1，f(2)=4，f(3)=3 这种数学题大家应该见过不少，其实思想就是层层递归，最终将目标值用 f(1)，f(2)，f(3)表示。
之前做个一个需求，需要实现类似操作系统文件夹的功能，我们用 MySQL 数据库记录数据，表字段有 4 列，分别是 id，index_name，pid，is_directory，index_name 记录文件或文件的名字，pid 记录它的父级 id，is_directory 标记它是文件还是文件夹。记录被存下以后，就涉及到取数据的问题了，我们前端需要的目标数据结构是这样的
col 1 | col 2 ------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3 | `[{``"id"``:1,``"name"``:``"./"``},{``"id"``:2,``"name"``:``"./1.txt"``},`
`{``"id"``:3,``"name"``:``"./dir1/"``},`
`{``"id"``:4,``"name"``:``"./dir1/2.txt"``},...]`
有点类似linux系统的tree命令。 </section> </section> </section></section>
复制代码
第一版代码是这样的：
</section> </section>
<section> <section> col 1 | col 2 ----------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | `tree = []`
`def getTree(pid):`
` ``return`
`for` `index ``in` `childIndexes:`
` ``if` `len(tree) == 0:`
` ``if` `index.is_directory==1 tree.append(`
`{``'id'``:index.``id``,``'name'``:``'./'``+index.index_name+``'/'``}) `
`getTree(index.``id``)`
` ``else``: `
`tree.append(`
`{``'id'``:index.``id``,``'name'``:``'/'``+index.index_name})`
` ``else``: `
` ``for` `item ``in` `tree: `
`if` `item[``'id'``] == index.``id`
` ``if` `item.is_directory==1: tree.append({``'id'``:index.``id``,``'name'``: `
`item[``'name'``]+index.index_name+``'/'``}) `
` ``else``: `
` ``tree.append`
`(`
`{``'id'``:index.``id``,``'name'``:item[``'name'``]+index.index_name`
`}`
`)` </section> </section> </section></section>
复制代码
大概看一下这个算法的时间复杂度，第一层的遍历时间复杂度是 n，第二层遍历的时间复杂度是 n，内层的时间复杂度是 O（n^2），再加上递归，最后的时间复杂度是 O（2^n*n^2），这个算法可见很粗糙，假如递归深度到是 100，最后执行效率简直会让人头皮发麻。接下来我们考虑一下如何优化。
第二版代码：
col 1 | col 2 ------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | `tree = []`
`def getTree(pid,path=``'./'``):`
` ``return`
` ``for` `index ``in` `childIndexes:`
` ``if` `len(tree) == 0: `
` ``if` `index.is_directory==1 tree.append({``'id'``:index.``id``,`
`'name'``:path+index.index_name+``'/'``}) `
` ``getTree(index.``id``, `
`path+index.index_name+``'/'``)`
` ``else``:`
` ``tree.append({``'id'``:index.``id``,`
`'name'``:path+index.index_name}) `
` ``else``: `
` ``if` `item.is_directory==1: tree.append({``'id'``:index.``id``,`
`'name'``:path+index.index_name+``'/'``})`
` ``else``: `
` ``tree.append({``'id'``:index.``id``,`
`'name'``:path+index.index_name})`
</section> </section>
<section> <section></section> </section> </section></section>
复制代码
我们用变量保存每一次的 path，这次我们看看时间复杂度是多少。第一层遍历时间复杂度是 O(n)，加上递归，最后的时间复杂度是 O(2^n*n)，不算太理想，最起码比第一次好点。
再看看一个面试的常见的题目，斐波拉契数列，n=1,1,3,5,8,13…，求第 n 位是多少？
一看首先就想到了递归的方式：
</section> </section> </section></section>
复制代码
1
2
3
4 | def fibSquence(n):
``if n ``in (1,2):
``return
``fibSquence(n-1)+ fibSquence(n-2)
这个算法的时间复杂度是 O(2^n)，关于时间复杂度具体看调用次数便能明白。我们考虑一下如何优化，比如求 n=3 是，需要先求 n=2,n=1，但是最开始 n=1,n=2 已经求过，多了两步重复计算。
下面是优化的代码：
</section> </section>
<section> <section> col 1 | col 2 ------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5 | `fibMap = {1:1,2:2}`
`def fibSquence(n):`
` ``else``:`
` ``result = fibSquence(n-1)+ fibSquence(n-2) fibMap.update({n:result})`
` ``return` `result` </section> </section> </section></section>
复制代码
我们用 map 报存中间值，map 是基于 hash 实现的，时间复杂度是 O(1)，这样这个算法的时间复杂度就是 O(n)。
但是事实上这个问题大可不必用递归方式求解
</section> </section>
<section> <section> col 1 | col 2 ---------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1
2
3
4
5
6 | `fibMap = {1:1,2:2}`
`def fibSquence(n):`
` ``else``:`
` ``for` `i ``in` `range(3,n+1): `
` ``fibMap.update({i:fibMap[i-1]+fibMap[i-2]})`
` ``return` `fibMap[n]` </section> </section> </section></section>
复制代码
这样我们只用一次遍历，便可以求出目标值。
递归算法的优化大概就是避免重复运算，将中金状态保存起来，以便下次使用，从结构上来看，是将时间复杂度转换为空间复杂度来解决。递归算法的效率其实是非常低的，能不用递归就尽量不用递归；当然了也要具体问题具体对待，比如说开始提到我做的项目遇到的问题，不用递归我还真想不出其他更好的方式解决。
本文转载自宜信技术学院网站。
原文链接：http://college.creditease.cn/detail/189
评论