為什么要用遞歸
遞歸是從數(shù)學(xué)領(lǐng)域的數(shù)學(xué)歸納法借鑒過來的一種技術(shù)。遞歸代碼通常比迭代代碼更加簡潔易懂腕铸。當(dāng)任務(wù)能夠被相似的子任務(wù)定義時(shí)惜犀，采用遞歸處理十分有效。二分排序和遍歷等問題往往有簡潔的遞歸解決方案汽烦。
遞歸函數(shù)的格式
if (判斷是否是基礎(chǔ)情況) {
return 該基礎(chǔ)情況下的函數(shù)的值
} else if (判斷是否為另一種基礎(chǔ)情況) {
return 該基礎(chǔ)情況下的函數(shù)的值
.
.
.
} else return (遞歸調(diào)用)
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);
}
遞歸和內(nèi)存
每次遞歸調(diào)用都會(huì)在內(nèi)存中生成一個(gè)新的函數(shù)副本莉御。分析上面的階乘函數(shù)：
recurse.png
每一次調(diào)用都會(huì)在程序運(yùn)行的棧內(nèi)存上創(chuàng)建一個(gè)函數(shù)副本，但是棧內(nèi)存是有限的礁叔，當(dāng)遞歸次數(shù)達(dá)到一個(gè)閾值的時(shí)候就會(huì)造成耗盡內(nèi)存，棧溢出錯(cuò)誤煮岁。
- 遞歸控制
- 嚴(yán)格定義遞歸函數(shù)的作用，包括函數(shù)画机、返回值新症，side-effect
- 先一般步氏，后特殊
- 每次調(diào)用必須縮小問題規(guī)模
- 每次問題規(guī)耐降縮小程度必須為1
eg:創(chuàng)建鏈表
public Node createLinkedList(List<Integer> data){
//最后考慮特殊情況
if(data.isEmpty()){
retrun null;
}
//先考慮一般情況，第一個(gè)成立隆嗅，然后n-1個(gè)成立
Node firstNode = new Node(data(0));
Node headOfSublist = createLinkedList(data.subList(1,data.size()));
firstNode.setNext(headOfSublist);
return firstNode;
}
eg:反轉(zhuǎn)鏈表
public Node reverseList(Node head){
//最后思考的特殊情況
if(head == null || head.getNext() == null){
return head;
}
//一般情況 假如他可以反轉(zhuǎn)鏈表得到出去第一個(gè)的剩下反轉(zhuǎn)
Node newHead = reverseList(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return newHead;
}
eg:給定一顆給定的二叉樹榛瓮，輸出所有的從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑
//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();
}
回溯
回溯是一種采用分治策略進(jìn)行窮舉搜索的方法。（有時(shí)候求解一個(gè)問題最好的方法就是嘗試所有的可能性）
- 二進(jìn)制串
- 生成k進(jìn)制串
- 背包問題
- 圖的著色問題
eg:從一個(gè)數(shù)組中列出取出n個(gè)元素的所有的組合
首先分解問題，選第一個(gè)元素坝锰，然后再剩下的數(shù)組中選n-1個(gè)；不選第一個(gè)元素顷级，然后從剩下的數(shù)組中選n個(gè)确垫。
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);
}
- 循環(huán)控制
- 定義循環(huán)不定式，并在循環(huán)體每次結(jié)束后保持循環(huán)不變式
- 先一般删掀，后特殊
- 每次必須向前推進(jìn)循環(huán)不變式中涉及的變量值
- 每次推進(jìn)的規(guī)模必須為1
eg：依然是上面的鏈表反轉(zhuǎn)的例子，用循環(huán)不定式實(shí)現(xiàn)
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();
}
}
}
保持并推進(jìn)反轉(zhuǎn)關(guān)系
- 邊界控制
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;
}
}
