递归是一种设计和描述算法的有力工具。 也是回溯法和动态规划的基础。
递归算法执行过程分 递推 和 回归 两个阶段
在 递推 阶段，将大的问题分解成小的问题
在 回归 阶段，获得最简单问题的解后，逐级返回，依次得到稍微复杂情况的解，知道获得最终的结果
1） 确定递归公式 , 比如 斐波那契数列 问题中的 fib(n)=fib(n-1)+fib(n-2)
2） 确定边界条件 bad case
自顶向下的递归，自底向上是迭代
递归运行效率较低，因为有函数调用的开销，递归多次也可能造成栈溢出。
void quicksort(int *a, int left, int right){
if (left<right)//加上这个，不然有死循环，造成堆栈溢出，这也是递归结束条件
{
int i = partion(a,left,right);//使得局部有序，i作为分隔
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
}归并排
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}二叉树
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}画递归树，可以很方便地看到是否存在重叠子问题，如果有的话，就可以采用动态规划。
- 斐波那契数列
- 阶乘计算
- 快速排序
- 链表翻转
- 很多树算法都是递归思想实现， 如 二叉树的最近公共祖先
- 梵塔问题 （三根针1，2，3表示，1号从小到大n个盘子，先要都移到3号上，不能出现大盘压小盘，找出移动次数最少的方案）
fib(n)=fib(n-1)+fib(n-2)
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
这个递归的算法效率非常差，存在大量重复计算。
我们可以有一个【缓存】，每次遇到一个子问题先去「缓存」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
public int fib(int n){
if (n == 0) return 0;
//缓存
int[] dp = new int[n + 1];
// base case
dp[0] = 0; dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
说一个细节优化点，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
int fib(int n) {
if (n < 1) return 0;
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
递归解法
public static LinkedNode mergeSeqLink2(LinkedNode l1, LinkedNode l2){
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.value < l2.value){
l1.next = mergeSeqLink2(l1.next,l2);
return l1;
}else{
l2.next = mergeSeqLink2(l2.next,l1);
return l2;
}
}
非递归解法
public static LinkedNode mergeSeqLink(LinkedNode l1, LinkedNode l2){
if (l1 == null) return l2;
if (l2 == null) return l1;
LinkedNode result = new LinkedNode(0);
LinkedNode tmp = result;
while (l1 != null && l2 != null) {
if (l1.value < l2.value) {
tmp.next = l1;
tmp = tmp.next; //tmp 指针前进
l1 = l1.next ; //l1 前进
} else {
tmp.next = l2;
l2 = l2.next;
tmp = tmp.next;
}
}
if (l1 != null) {
tmp.next = l1;
}
if (l2 != null) {
tmp.next = l2;
}
return result.next;
}
链表翻转 代码参考这里
//翻转链表前n个节点
static LinkedNode tmp;//需要一个外部的临时变量
public static LinkedNode reverseN(LinkedNode head, int n){
//LinkedNode tmp = null;
if (n == 1) {
tmp = head.next;
return head;
}
LinkedNode tail = reverseN(head.next, n-1);
head.next.next = head; //后n-1个节点 与 第 1 个节点 指向 翻转
head.next = tmp;
return tail;
}二叉树的最近公共祖先 代码参考这里
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// base case
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 情况 1 ：p, q 在 root 为根的树中
if (left != null && right != null) {
return root;
}
// 情况 2 ：p, q 不在 在 root 为根的树中
if (left == null && right == null) {
return null;
}
// 情况 3 ： p, q 只有1个在root 为根的树中
return left == null ? right : left;
}