一、初识递归
递归函数 = 终止条件 + 递归关系
终止条件：当大问题被拆解成能轻松解决的小问题时，运行终止条件中的逻辑
递归关系：定义如何将大问题拆解为小问题
例子：小名跑步。
例如：小名跑 4 公里，能够分为（跑 1km+ 再跑 3km）->（跑 1km+ 再跑 2km）->（跑 1km+ 再跑 1km）->（跑齐全程）
实现：
public void running(int distance) {
if (distance == 0) {// 终止条件
System.out.println(“ 小名跑完了全程！”);
return;
} else {
System.out.println(“ 小名跑了 1km”);
distance = distance – 1;
System.out.println(“ 还剩 ” + distance + “km”);
running(distance); // 递归调用
}
}
@Test
public void test1() {
int distance = 4;
System.out.println(“ 跑步总程：” + distance + “km”);
running(distance);
}
输入：
跑步总程：4km
小名跑了 1km
还剩 3km
小名跑了 1km
还剩 2km
小名跑了 1km
还剩 1km
小名跑了 1km
还剩 0km
小名跑完了全程！
正如：二叉搜寻树中的搜寻
树对象：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return “TreeNode{” +
“val=” + val +
“, left=” + left +
“, right=” + right +
‘}’;
}
}
次要办法：
public TreeNode searchBST(TreeNode root, int val) {
// 终止条件
if (root == null) return null; // 搜寻完所有节点，指标节点不存在
if (root.val == val) return root; // 以后节点即为指标节点
// 递归(已知：二叉搜寻树（BST）右子树节点值大于左子树节点值)
if (val > root.val) return searchBST(root.right, val); // 目标值大于以后节点，开始搜寻右子树
else return searchBST(root.left, val); // 目标值大于以后节点，开始搜寻左子树
}
测试：
@Test
public void test() {
TreeNode treeNode1 = new TreeNode(1);
TreeNode treeNode3 = new TreeNode(3);
TreeNode treeNode7 = new TreeNode(7);
TreeNode treeNode2 = new TreeNode(2,treeNode1,treeNode3);
TreeNode treeNode4 = new TreeNode(4,treeNode2,treeNode7);
TreeNode treeNode = searchBST(treeNode4, 2);
System.out.println(treeNode == null ? null : treeNode.toString());
}
输入：
TreeNode{val=2, left=TreeNode{val=1, left=null, right=null}, right=TreeNode{val=3, left=null, right=null}}
递归三种模式：
1.Memorization 缓存：将计算结果保留，防止反复计算
2.Divide and conquer 分治：将一个大问题分解成小问题，各个击破，而后将“小问题的解”组合起来
3.Backracking 回溯：逐渐尝试所有满足条件的后果，一旦发现不可行的解，立刻进行。
二、缓存
初始化缓存
如果缓存中存在答案，则间接返回
将计算结果写入缓存
正如：斐波那契数
题目提醒中提到：
f(0) = 0，f(1) = 1
f(n) = f(n – 1) + f(n – 2)，其中 n > 1
所以我不难计算出 f(2)=1，从上图咱们能够看出 f(2)被计算了两次，所以这里咱们用缓存来缩小加法的次数。
public int fib(int n) {
//1. 初始化缓存
int[] memo = new int[n+1];
int res = helper(memo, n);
return res;
}
public int helper(int[] memo, int n){
if (n < 2) {
return n;
}
//2. 如果缓存中存在答案，则间接返回
if(memo[n]!=0){
return memo[n];
}
//3. 将计算结果写入缓存
memo[n] = helper(memo, n – 1) + helper(memo, n – 2);
return memo[n];
}
测试：
@Test
public void test3(){
int fib = fib(4);
System.out.println(fib);
}
输入：
3
1
三、分治
把大问题分为一系列小问题
递归求解每个子问题
合并每个子问题的后果
二叉搜寻树（BST）：左子树的所有值要比根节点小；右子树的所有值要比根节点大
正如：LeetCode：98. 验证二叉搜寻树
public boolean isValidBST(TreeNode root) {
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean helper(TreeNode node, long lower, long upper){
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return helper(node.left,lower,node.val) && helper(node.right,node.val,upper);
}
helper 办法解读：
当入参是左子树节点，要限度所有其余节点比该节点小（限度上界是节点 val）
当入参是右子树节点，要限度所有其余节点比根节点大（限度下界是节点 val）
省略树对象：见上一大节
测试：
@Test
public void test5(){
System.out.println(“————– 示例 1 ————–“);
TreeNode treeNode11 = new TreeNode(1);
TreeNode treeNode33 = new TreeNode(3);
TreeNode treeNode22 = new TreeNode(2,treeNode11,treeNode33);
System.out.println(isValidBST(treeNode22));
System.out.println(“————— 示例 2 ————-“);
TreeNode treeNode1 = new TreeNode(1);
TreeNode treeNode3 = new TreeNode(3);
TreeNode treeNode6 = new TreeNode(6);
TreeNode treeNode4 = new TreeNode(4, treeNode3, treeNode6);
TreeNode treeNode5 = new TreeNode(5, treeNode1, treeNode4);
System.out.println(isValidBST(treeNode5));
}
示例 1：
示例 2：
输入：
————– 示例 1 ————–
true
————— 示例 2 ————-
false
1
2
3
4
四、回溯
迭代所有可能的候选对象
试试这个局部候选解决方案
给定候选者，进一步摸索
回溯
正如：括号生成
从上文的例子中，能够看出递归的题目都能够被画成树状图。本题要求是“无效的”括号组合，所以必定不可能由右括号开始。之后就是尝试列举所有括号组合状况了，当括号数量达到 2n 这就是咱们的终止递归的条件了。这里值得注意的是：左括号的数量不能大于 n，而且右括号的数量不能大于左括号的数量，显然这样是不合乎题目“无效的”括号组合规定的
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
// 终止条件
if (cur.length() == 2 * max) {
ans.add(cur.toString());
return;
}
// 左括号不能超过最大值
if (open < max) {
// 试探增加左括号
backtrackV2(ans, cur.append(“(“), open + 1, close, max);
// 回溯
cur.deleteCharAt(cur.length() – 1);
}
// 右括号数量不能大于左括号数量
if (close < open) {
// 试探增加右括号
backtrackV2(ans, cur.append(“)”), open, close + 1, max);
// 回溯
cur.deleteCharAt(cur.length() – 1);
}
}
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
测试
@Test
public void test6(){
List<String> strings = generateParenthesis(3);
System.out.println(strings);
}
输入：
[((())), (()()), (())(), ()(()), ()()()]