1 定义

  • devide : devide the problem (instance) into one or more subproblem;
  • conquer: 步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归， 直接求解
  • combine:步骤将子问题组合成原问题的解

2 思想应用

  • merge sort
  • binary search
  • pow
  • fib(斐波那契问题)

3 fib

1 直接求解

  • 利用递归终止的条件， fib(n) = fib(n-1)+fib(n-1);

2 利用数组记录fib从 1 到 n 的每种解法(动态规划)

  1. fib(n)= { n  (n<=1);
  2.         { fib(n-1) + fib(n-2) (n >=2)
  4. public  int fib(int n){
  5.             return  (2 >n)? n:
  6.                      fib(n-1) + fib(n-2);
  7.         }
  10. public int fib(int n){
  11.     int[] res = new int[n+1];
  12.     res[1] = 1;
  13.     res[2] = 1;
  14.     for(int  i = 3; i<= n; i++){
  15.         res[i] = res[i-1]+res[i-2];
  16.     }
  17.     return res[n];
  18. }
  1. Iterator
  4. public int fib(int n){
  5.     int first = 0, last = 1;
  6.     while(0 < n--) {
  7.          last  = last + first;
  8.         first = last - first;
  9.         }
  10.     return last;
  11.     }


3 利用矩阵

  • 将n 分为[ [ n, n-1], [n-1, n-2] ];

2 递归

1 基本思想

  • 递归是每个函数直接或间接的调用自身问题的求解过程
  • 划分为许多相同性质的在子问题的求解
  • 而小问题的求解过程可以容易的求出
  • 这些子问题的解就构成原问题的解

2 总体思想

  • 待求解问题的解 -> 输入变量下的函数f(x);
  • 通过寻找函数g()， 使得发f(x) = g(f(x-1));
  • 且已经知道发f(0), 就可以通过f(0)和 g()求出f(x)的值
  1. public int  f(int x){
  2.     if(x == 0)  x=0; // f(0)
  3.     else x+f(x-1); // g()
  4. }
  6. int ans = 0
  7. for(int i = 0; i<=x; i++){
  8.     ans += i;
  9. }

1 key

  • 递归式： 如何将原问题划分为子问题
  • 递归出口： 递归终止的条件， 即最小子问题的求解， 可以允许多个出口
  • 界函数： 问题规模变化的函数， 它保证递归的规模向出口条件靠拢

3 线性递归 & 减而治之

  • 线性递归
  • 减而治之： 每深入一层， 待解决的问题的规模都缩减一个常数，

4 递归 栈 循环

  • 栈 是 递归实现的本质， 递归也可以用循环来实现
  1. public int f(int x){
  2.     if(x == 1)  return 1;
  3.     else       x*f(x-1); 
  4. }
  7. public int loop(int n){
  8.     int res = 1;
  9.     for(int i =1; i<=n; i++){
  10.         res *= i;
  11.         return res;
  12.     }
  13. }

分治与递归 - 图1

4 递归与迭代

  • 迭代是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
  1. 这里是二分法解方程的递归和迭代算法的比较。
  3. 递归：
  4. 确定开区间左边界和右边界，(L, R)
  5. 若L + 1 >= R（即不包含整数点），表示序列中不存在f(x)
  6. 取中位 M = (L + R) / 2
  7. 若f(M) == y，返回M
  8. 否则根据f(M)和y的关系递归查找(L, M)或(M, R)
  11. 迭代：
  12. 确定边界(L, R)
  13. while (L + 1 < R) / 区间中包含整点 /
  14. 求中位M = (L + R) / 2
  15. 若f(M)等于y，退出循环
  16. 根据f(M)与y的关系执行 L = M 或 R = M，进入下一轮循环

5 尾递归

  • 尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。SICP中描述了一个内存占用曲线

  • 尾递归主要是对栈空间的优化，这个优化是 0 -1 ，是一个常数优化，不花对带来质的变化，

public int tail(x, total){
    if( x == 0)  return total;
    else         tail(x-1, total+x);
}

3 两个或多个出口的递归

1 相同的树

定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q== null ) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val )    return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}