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 的每种解法(动态规划)
fib(n)= { n (n<=1);
{ fib(n-1) + fib(n-2) (n >=2)
public int fib(int n){
return (2 >n)? n:
fib(n-1) + fib(n-2);
}
public int fib(int n){
int[] res = new int[n+1];
res[1] = 1;
res[2] = 1;
for(int i = 3; i<= n; i++){
res[i] = res[i-1]+res[i-2];
}
return res[n];
}
Iterator
public int fib(int n){
int first = 0, last = 1;
while(0 < n--) {
last = last + first;
first = last - first;
}
return last;
}
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)的值
public int f(int x){
if(x == 0) x=0; // f(0)
else x+f(x-1); // g()
}
int ans = 0
for(int i = 0; i<=x; i++){
ans += i;
}
1 key
- 递归式: 如何将原问题划分为子问题
- 递归出口: 递归终止的条件, 即最小子问题的求解, 可以允许多个出口
- 界函数: 问题规模变化的函数, 它保证递归的规模向出口条件靠拢
3 线性递归 & 减而治之
- 线性递归
- 减而治之: 每深入一层, 待解决的问题的规模都缩减一个常数,
4 递归 栈 循环
- 栈 是 递归实现的本质, 递归也可以用循环来实现
public int f(int x){
if(x == 1) return 1;
else x*f(x-1);
}
public int loop(int n){
int res = 1;
for(int i =1; i<=n; i++){
res *= i;
return res;
}
}
4 递归与迭代
- 迭代是重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”,而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
这里是二分法解方程的递归和迭代算法的比较。
递归:
确定开区间左边界和右边界,(L, R)
若L + 1 >= R(即不包含整数点),表示序列中不存在f(x)
取中位 M = (L + R) / 2
若f(M) == y,返回M
否则根据f(M)和y的关系递归查找(L, M)或(M, R)
迭代:
确定边界(L, R)
while (L + 1 < R) / 区间中包含整点 /
求中位M = (L + R) / 2
若f(M)等于y,退出循环
根据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);
}
}