1、引言
今天我們來學習遞歸，如果單說學習算法， 遞歸併不能說是算法，而是一種編程的手法，為什麼現在要學習這個呢？因為後面在學習其他算法時，要牽涉一些遞歸的調用方法，是為以後理解學習的內容做好鋪墊。
遞歸方法作為一種優雅的解題方法，是大多數程式設計師比較喜歡的編寫方式之一。遞歸把程式設計師分為三類：一種是恨它的，第二種是愛它的，最後一種是恨了一段時間之後接觸之後又愛上了它。我平時編寫代碼的時候可能很少用到，但我對遞歸的印象還是蠻喜歡的。今天就來比較深入的學習一下遞歸的相關知識吧。
2、遞歸
2.1.1 什麼是遞歸
遞歸說白了就是用一個函數不斷調用自己的過程，遞歸的使用可以讓代碼邏輯很清晰，但並沒有實質性能的提升。實質上，在有些情況下，使用循環的性能可能會更佳。
2.1.2 遞歸中的兩大元帥
上面介紹到遞歸是一個函數不斷調用自己的過程，但如果沒有限制結束調用的條件，就會讓遞歸無限的循環下去。於是編寫遞歸函數時，必須告訴函數什麼時候要停止遞歸調用。這就引出了遞歸的兩大元帥，分別為基線條件（base case）和遞歸條件（recursive case)。遞歸條件是指讓函數調用自身，而基線條件就是通知函數不要再調用自己，從而避免了無限循環。
2.2.1 棧
使用遞歸必須需要了解棧的概念，棧是一種簡單的數據結構，它的特點可以舉一個簡單的例子你就明白了。在餐廳吃飯的時候，我們通常是在收銀臺進行點餐，然後點餐付款成功之後會將信息傳送給後廚師傅手裡，以一個先來後到的原則，廚師每次看到的信息都是最早來點餐的人的信息，而且做完之後便刪掉了這個點餐信息，接著去做下一個人點的餐，而收銀員每回都只在待做餐列表中添加點餐信息，而不管究竟現在有多少點餐信息。因此這個待做餐列表就只有兩種操作：存入和刪除。棧這種數據結構就是這麼一個工作原理，理解了這個原理之後，我們就可以繼續後面的內容了。
2.2.2 調用棧
計算機在內部使用被稱為調用棧的棧。以一段代碼解釋一下計算機是如何調用棧的。
public static void main(String[] args) {
//調用方法1
Greet("努力的浩浩");
}
//定義一個問候的方法1
private static void Greet(String name){
System.out.println("hello,"+name+"!");
Greet2(name);
System.out.println("getting ready to say bye");
bye();
}
//定義一個問候的方法2
private static void Greet2(String name){
System.out.println("how are you,"+name+"?");
}
//定義一個再見的方法
private static void bye(){
System.out.println("ok,bye!");
}
下面詳細介紹調用函數時內存的變化情況。
如main方法中調用了Greet("努力的浩浩");計算機會為該方法開闢一塊內存空間，且存儲變量name的值為"努力的浩浩"，接下來執行該方法，列印出"hello，努力的浩浩！"之後，程序開始執行Greet2的方法。
當然，計算機也會為這個方法開闢一塊內存空間，並且存儲變量name的值為"努力的浩浩"。那麼這兩個方法執行的過程中，計算機就開闢了兩個內存單元，於是乎計算機採用棧存儲這些內存塊，其中第二個內存單元位於第一個內存塊的上方，列印出"how are you，努力的浩浩？"之後，從Greet2()方法中返回，此時，棧頂被彈出，於是Greet()中的變量成為了棧頂，而繼續執行程序，應先列印出"getting ready to say bye"之後，再調用bye()列印出"ok,bye!"的語句。
上面這個棧由於存儲了多個函數的變量，稱為了調用棧。
2.2.3 遞歸調用棧
遞歸函數其實也是使用的是調用棧，我們先來定義一個遞歸函數，該函數完成的功能就是求數的階乘，函數名為factorial，
如factorial(5)記作5！，其定義為5！= 5 x 4 x 3 x 2 x 1。下面是遞歸函數階乘的代碼！
//定義一個遞歸函數階乘
private static int factorial(int number){
if(number == 1)
{
return 1;
}
else {
return number * factorial(number - 1);
}
}
下面以一幅圖來講解遞歸調用棧的原理，詳細分析fact（3）調用棧是如何變化的。
2.3 溫馨提示
使用棧雖然很方便，但是也有很大代價：如果要存儲信息可能需要大量內存，每個函數調用都將佔用內存，如果棧摞的很高必將
導致計算機存儲大量函數調用的信息。這個時候怎麼辦呢？
有兩種解決方案：
1、使用循環
2、使用尾遞歸（這個我也不懂是啥，書上就是這麼寫的，並非所有程式語言都支持尾遞歸）