算法-递归

Posted on | In |

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

如何编写递归代码？

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归弊端

堆栈溢出（限制递归调用的最大深度)

重复计算（通过一个数据结构（比如散列表）来保存已经求解过的 f(k)，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算）

函数调用耗时多

空间复杂度高

我们平时调试代码喜欢使用 IDE 的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？

调试递归:
1.打印日志发现，递归值。
2.结合条件断点进行调试。

分治公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
divide_conquer(problem, param1, param2, ...)

# recursion terminator
if problem结束
	print_result
	return
	
#prepare data
data = prepare_data(problem)
subproblems = split_proble(problem, data)

# conquer subproblems
subresult1 = self.divide_conquer(subproblesm[0], p1,...)
subresult2 = self.divide_conquer(subproblesm[1], p1,...)
...

# process and generate the final result
result = process_result(subresult1, subresult2, subresult3, ...)

递归公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
recursion(level, param1, param2, ...)

# recursion terminator
if level > MAX_LEVEL
	print_result
	return
	
#prepare logic in current level
process_data(level, data, ...)

# drill down
self.recursion(level + 1, p1, ...)

# reverse the current level status if needed
reverse_state(level)