Resursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Java
public void recursion(int level, int param) { 
    // 1 recursion terminator  1.递归终结者，递归中止的条件
  if (level > MAX_LEVEL) { 
    // 处理结果 process_result
    return; 
  }
    // 2 process logic in current level  2.处理当前层逻辑
  process(level, param); 
  　// 3 drill down  3.下探到下一层
  recur( level: level + 1, newParam); 
    // 4 revert the current level status if needed  4.清理当前层（比如需要清理的全局变量），不是必选项
 
}

Divide & Conquer

Divide&Conquer is a special kind of recursion. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// java
public void divide_conquer(problem, param1, param2, ...){
    // 1 recursion terminator 终止条件
    if problem is None:
        // print_result
        return
    // 2 prepare data  处理当前层逻辑
    data = prepare_data(problem);
    subproblems = split_problem(problem, data);
    // 3 conquer subproblems  调用函数下探到下一层，解决更细节的子问题
    subresult1 = divide_conquer(subproblems[0], p1, ...);
    subresult2 = divide_conquer(subproblems[1], p1, ...);
    subresult3 = divide_conquer(subproblems[2], p1, ...);
    ...
    // 4 process and generate the final result
    result = process_result(subresult1, subresult2, subresult3, ...)
​
    // 5 revert the current level states if needed
}      
     
    // the difference between normal recursion and Divide&Conquer is adding one step - merge and return sub-results between drill down and revert state  
    // 与泛型递归不同就是在drill down与revert state中间加了一步
    // 就是把drill down得到的子结果要合并在一起，返回回去。

算法漫游指北（第十篇）:泛型递归、递归代码模板、递归思维要点、分治算法、回溯算法