为什么要用递归
递归是从数学领域的数学归纳法借鉴过来的一种技术。递归代码通常比迭代代码更加简洁易懂。当任务能够被相似的子任务定义时，采用递归处理十分有效。二分排序和遍历等问题往往有简洁的递归解决方案。
递归函数的格式
if (判断是否是基础情况) {
return 该基础情况下的函数的值
} else if (判断是否为另一种基础情况) {
return 该基础情况下的函数的值
.
.
.
} else return (递归调用)
eg: 阶乘为例
n!=1 n = 0
n! = n * (n - 1)! n > 0
int fact(int n) {
if (n == 1) return 1;
else if (n == 0) return 1;
else return n * fact(n-1);
}
递归和内存
每次递归调用都会在内存中生成一个新的函数副本。分析上面的阶乘函数：
recurse.png
每一次调用都会在程序运行的栈内存上创建一个函数副本，但是栈内存是有限的，当递归次数达到一个阈值的时候就会造成耗尽内存，栈溢出错误。
- 递归控制
- 严格定义递归函数的作用，包括函数、返回值，side-effect
- 先一般，后特殊
- 每次调用必须缩小问题规模
- 每次问题规模缩小程度必须为1
eg:创建链表
public Node createLinkedList(List<Integer> data){
//最后考虑特殊情况
if(data.isEmpty()){
retrun null;
}
//先考虑一般情况，第一个成立，然后n-1个成立
Node firstNode = new Node(data(0));
Node headOfSublist = createLinkedList(data.subList(1,data.size()));
firstNode.setNext(headOfSublist);
return firstNode;
}
eg:反转链表
public Node reverseList(Node head){
//最后思考的特殊情况
if(head == null || head.getNext() == null){
return head;
}
//一般情况 假如他可以反转链表得到出去第一个的剩下反转
Node newHead = reverseList(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return newHead;
}
eg:给定一颗给定的二叉树，输出所有的从根结点到叶子结点的路径
//time: O(n) space: O(n)
public void printPaths(BinaryTreeNode root){
int[] path = new int[256];
printPaths(root, path, 0);
}
public void printPaths(BinaryTreeNode root, int[] path, int pathLength){
if (root == null) {
return;
}
path[pathLength] = root.getData();
pathLength++;
if (root.getLeft() == null && root.getRight() == null) {
printArray(path, pathLength);
}else {
printPaths(root.getLeft(), path, pathLength);
printPaths(root.getRight(), path, pathLength);
}
}
public printArray(int[] path, int pathLength){
for (int i = 0; i < pathLength; i++) {
System.out.print(""+path[i]);
}
System.out.println();
}
回溯
回溯是一种采用分治策略进行穷举搜索的方法。（有时候求解一个问题最好的方法就是尝试所有的可能性）
- 二进制串
- 生成k进制串
- 背包问题
- 图的着色问题
eg:从一个数组中列出取出n个元素的所有的组合
首先分解问题，选第一个元素，然后再剩下的数组中选n-1个；不选第一个元素，然后从剩下的数组中选n个。
public void combinations(List<Integer> selected, List<Integer> data, int n){
if(n == 0){
for(Integer i : seleted){
System.out.print(i+"");
}
return;
}
if(data.isEmpty()){
return;
}
//selected first element
seleted.add(data.get(0));
combinations(selected, data.sublist(1,data.size()));
//unselect first element
selected.remove(selected.size() - 1);
combinations(selected, data.sublist(1, data.size()), n);
}
- 循环控制
- 定义循环不定式，并在循环体每次结束后保持循环不变式
- 先一般，后特殊
- 每次必须向前推进循环不变式中涉及的变量值
- 每次推进的规模必须为1
eg：依然是上面的链表反转的例子，用循环不定式实现
public Node reverseLinkedList(Node head){
Node newHead = null;
Node curHead = head;
while(curHead != null) {
Node next = curHead.getNext();
curHead.setNext(newHead);
newHead = curHead;
curHead = next;
}
return newHead;
}
eg:链表中delete_if
public void deleteIfEquals(Node head, int value){
while(head != null && head.getValue() == value){
head = head.getNext();
}
if(head == null){
return null;
}
Node prev = head;
while(prev.getNext() != null){
if(prev.getNext().getValue() == value){
prev.getNext().setNext(prev.getNext().getNext());
}else{
prev = prev.getNext();
}
}
}
保持并推进反转关系
- 边界控制
eg:二分查找
public int binarySearch(int[] arr, int k){
int a = 0;
int b = arr.length();
while(a < b){
int m = a + (b - a) /2;
if(k < arr[m]){
b = m;
}else if(k > arr[m]){
a = m + 1;
}else {
return m;
}
return -1;
}
}
