最新情報(bào)：所有的遞歸都可以改寫成非遞歸？
關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！
前言
本文收錄于專輯：http://dwz.win/HjK，點(diǎn)擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識。
你好，我是彤哥，一個(gè)每天爬二十六層樓還不忘讀源碼的硬核男人。
上一節(jié)，我們使用位圖介紹了12306搶票算法的實(shí)現(xiàn)，沒有收到推送的同學(xué)可以點(diǎn)擊上方專輯查看，或者在公主號歷史消息中查看。
在上一節(jié)的最后，彤哥收到最新情報(bào)，說是所有的遞歸都可以改寫成非遞歸，是不是真的呢？如何實(shí)現(xiàn)呢？有沒有套路呢？
讓我們帶著這些問題進(jìn)入今天的學(xué)習(xí)吧。
何為遞歸？
所謂遞歸，是指程序在運(yùn)行的過程中調(diào)用自身的行為。
這種行為也不能無限制地進(jìn)行下去，得有個(gè)出口，叫做邊界條件，所以，遞歸可以分成三個(gè)段：前進(jìn)段、達(dá)到邊界條件，返回段，在這三個(gè)段我們都可以做一些事，比如前進(jìn)段對問題規(guī)模進(jìn)行縮小，返回段對結(jié)果進(jìn)行整理。
這么說可能比較抽象，讓我們看一個(gè)簡單的案例：
如何用遞歸實(shí)現(xiàn)1到100的相加？
1到100相加使用循環(huán)大家都會(huì)解，代碼如下：
public class Sum {
public static void main(String[] args) {
System.out.println(sumCircle(1, 100));
}
private static int sumCircle(int min, int max) {
int sum = 0;
for (int i = min; i <= max; i++) {
sum += i;
}
return sum;
}
}
那么，如何使用遞歸實(shí)現(xiàn)呢？
如何快速實(shí)現(xiàn)遞歸？
首先，我們要找到這道題的邊界條件，1到100相加，邊界條件可以是1，也可以是100，如果從1開始，那么邊界條件就是100，反之亦然。
找到了邊界條件之后，就是將問題規(guī)模縮小，對于這道題，計(jì)算1到100相加，那么，能不能先計(jì)算1到99相加再把100加上呢？肯定是可以的，這樣問題的規(guī)模就縮小了，直到，問題規(guī)模縮小為1到1相加為止。
OK，讓我們看代碼實(shí)現(xiàn)：
private static int sumRecursive(int min, int max) {
// 邊界條件
if (min >= max) {
return min;
}
// 問題規(guī)模縮小
int sum = sumRecursive(min, max - 1);
// 加上當(dāng)前值
sum += max;
// 返回
return sum;
}
是不是很簡單？還可以更簡單：
private static int sumRecursive2(int min, int max) {
return min >= max ? min : sumRecursive2(min, max - 1) + max;
}
686?
所以，使用遞歸最重要的就是找到邊界條件，然后讓問題的規(guī)模朝著邊界條件的方向一直縮小，直到達(dá)到邊界條件，最后依次返回即可，這也是快速實(shí)現(xiàn)遞歸的套路。
這么看來，使用遞歸似乎很簡單，但是，它有沒有什么缺點(diǎn)呢？
要了解缺點(diǎn)就得從遞歸的本質(zhì)入手。
遞歸的本質(zhì)是什么？
我們知道，JVM啟動(dòng)的時(shí)候有個(gè)參數(shù)叫做-Xss，它不是表示XSS攻擊哈，它是指每個(gè)線程可以使用的線程棧的大小。
那么，什么又是線程棧呢？
棧大家都理解了，我們在前面的章節(jié)也學(xué)習(xí)過了，使用棧，可以實(shí)現(xiàn)計(jì)算器的功能，非常方便。
線程棧，顧名思義，就是指線程運(yùn)行過程中使用的棧。
那么，線程在運(yùn)行的過程中為什么要使用棧呢？
這就不得不說方法調(diào)用的本質(zhì)了。
舉個(gè)簡單的例子：
private static int a(int num) {
int a = 1;
return a + b(num);
}
private static int b(int num) {
int b = 2;
return c(num) + b;
}
private static int c(int num) {
int c = 3;
return c + num;
}
在這段代碼中，方法a() 調(diào)用 方法b()，方法b() 調(diào)用 方法c()，在實(shí)際運(yùn)行的過程中，是這樣處理的：調(diào)用方法a()時(shí)，發(fā)現(xiàn)需要調(diào)用方法b()才能返回，那就把方法a()及其狀態(tài)保存到棧中，然后調(diào)用方法b()，同樣地，調(diào)用方法b()時(shí)，發(fā)現(xiàn)需要先調(diào)用方法c()才能返回，那就把方法b()及其狀態(tài)入棧，然后調(diào)用方法c()，調(diào)用方法c()時(shí)，不需要額外調(diào)用別的方法了，計(jì)算完畢返回，返回之后，從棧頂取出方法b()及當(dāng)時(shí)的狀態(tài)，繼續(xù)運(yùn)行方法b()，方法b()運(yùn)行完畢，返回，再從棧中取出方法a()及當(dāng)時(shí)的狀態(tài)，計(jì)算完畢，方法a()返回，程序等待結(jié)束。
還是上圖吧：
所以，方法調(diào)用的本質(zhì)，就是棧的使用。
同理，遞歸的調(diào)用就是方法的調(diào)用，所以，遞歸的調(diào)用，也是棧的使用，不過，這個(gè)棧會(huì)變得非常大，比如，對于1到100相加，就有99次入棧出棧的操作。
因此，總結(jié)起來，遞歸有以下兩個(gè)缺點(diǎn)：
操作耗時(shí)，因?yàn)闋可娴酱罅康娜霔３鰲２僮鳎?/p>
有可能導(dǎo)致線程棧溢出，因?yàn)檫f歸調(diào)用占用了線程棧很大的空間。
那么，我們是不是就不要使用遞歸了呢？
當(dāng)然不是，之所以使用遞歸，就是因?yàn)樗褂闷饋矸浅：唵危軌蚩焖俚亟鉀Q我們的問題，合理控制遞歸調(diào)用鏈的長度，就是一個(gè)好遞歸。
既然，遞歸調(diào)用的本質(zhì)，就是棧的使用，那么，我們能不能自己模擬一個(gè)棧，將遞歸調(diào)用改成非遞歸呢？
當(dāng)然可以。
修改遞歸為非遞歸的套路
還是使用上面的例子，現(xiàn)在我們需要把遞歸修改成非遞歸，且不是使用for循環(huán)的那種形式，要怎么實(shí)現(xiàn)呢？
首先，我們要自己模擬一個(gè)棧；
然后，找到邊界條件；
最后，朝著邊界條件的方向縮小問題規(guī)模；
OK，上代碼：
private static int sumNonRecursive(int min, int max) {
int sum = 0;
// 聲明一個(gè)棧
Stack stack = new Stack();
stack.push(max);
while (!stack.isEmpty()) {
if (max > min) {
// 要計(jì)算max，先計(jì)算max-1
stack.push(--max);
} else {
// 問題規(guī)模縮小到一定程度，計(jì)算返回
sum += stack.pop();
}
}
return sum;
}
好了，是不是很簡單，其實(shí)跟遞歸的套路是一樣的，只不過改成自己模擬棧來實(shí)現(xiàn)。
這個(gè)例子可能不是那么明顯，我們再舉個(gè)二叉樹遍歷的例子來看一下。
public class BinaryTree {
Node root;
// 插入元素
void put(int value) {
if (root == null) {
root = new Node(value);
} else {
Node parent = root;
while (true) {
if (value <= parent.value) {
if (parent.left == null) {
parent.left = new Node(value);
return;
} else {
parent = parent.left;
}
} else {
if (parent.right == null) {
parent.right = new Node(value);
return;
} else {
parent = parent.right;
}
}
}
}
}
// 先序遍歷
void preTraversal(Node x) {
if (x == null) return;
System.out.print(x.value + ",");
preTraversal(x.left);
preTraversal(x.right);
}
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.put(3);
binaryTree.put(1);
binaryTree.put(2);
binaryTree.put(7);
binaryTree.put(8);
binaryTree.put(5);
binaryTree.put(4);
binaryTree.put(6);
binaryTree.put(9);
binaryTree.put(0);
binaryTree.preTraversal(binaryTree.root);
}
}
我這里隨手寫了一顆二叉樹，并實(shí)現(xiàn)了其先序遍歷，這個(gè)測試用例中的二叉樹長這個(gè)樣子：
所以，這個(gè)二叉樹的先序遍歷結(jié)果為3,1,0,2,7,5,4,6,8,9,。
可以看到，使用遞歸先序遍歷二叉樹非常簡單，而且代碼清晰易懂，那么，它如何修改為非遞歸實(shí)現(xiàn)呢？
首先，我們要自己模擬一個(gè)棧；
然后，找到邊界條件，為節(jié)點(diǎn)等于空時(shí)；
最后，縮小問題規(guī)模，這里是先把右子樹壓棧，再把左子樹壓棧，因?yàn)橄茸蠛笥遥?/p>
好了，來看代碼實(shí)現(xiàn)：
// 先序遍歷非遞歸形式
void nonRecursivePreTraversal(Node x) {
// 自己模擬一個(gè)棧
Stack stack = new Stack();
stack.push(x);
while (!stack.isEmpty()) {
Node tmp = stack.pop();
// 隱含的邊界條件
if (tmp != null) {
System.out.print(tmp.value + ",");
// 縮小問題規(guī)模
stack.push(tmp.right);
stack.push(tmp.left);
}
}
}
掌握了這個(gè)套路是不是把遞歸改寫為非遞歸非常簡單，不過，改寫之后的代碼顯然沒有遞歸那么清晰。
好了，遞歸改寫為非遞歸的套路我們就講到這里，不知道你Get到了沒有呢？你也可以找個(gè)遞歸自己來改寫試試看。
后記
本節(jié)，我們從遞歸的概念入手，學(xué)習(xí)了如何快速實(shí)現(xiàn)遞歸，以及遞歸的本質(zhì)，最后，學(xué)習(xí)了遞歸改寫為非遞歸的套路。
本質(zhì)上，這也是棧這種數(shù)據(jù)結(jié)構(gòu)的常規(guī)用法。
既然講到了棧，不講隊(duì)列是不是有點(diǎn)過分？
所以，下一節(jié)，遍歷各種源碼的彤哥將介紹如何實(shí)現(xiàn)高性能的隊(duì)列，想了解其中的套路嗎？還不快點(diǎn)來關(guān)注我！
關(guān)注公號主“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識。