递归是从数学领域的数学归纳法借鉴过来的一种技术。递归代码通常比迭代代码更加简洁易懂。当任务能够被相似的子任务定义时,采用递归处理十分有效。二分排序和遍历等问题往往有简洁的递归解决方案。
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
每一次调用都会在程序运行的栈内存上创建一个函数副本,但是栈内存是有限的,当递归次数达到一个阈值的时候就会造成耗尽内存,栈溢出错误。
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;
}
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;
}
//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();
}
回溯是一种采用分治策略进行穷举搜索的方法。(有时候求解一个问题最好的方法就是尝试所有的可能性)
首先分解问题,选第一个元素,然后再剩下的数组中选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);
}
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();
}
}
}
保持并推进反转关系
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;
}
}