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、使用尾遞歸（這個我也不懂是啥，書上就是這么寫的，并非所有編程語言都支持尾遞歸）
