總結(jié)的寫遞歸的幾種方法：
第一種是直接有遞推公式玄帕，那么就直接找停止條件就好了畏纲，但是要注意停止條件的嚴(yán)謹(jǐn)性镜沽。如果條件不嚴(yán)謹(jǐn)可能會出現(xiàn)死循環(huán)的情況茵乱。
比如 斐波那契數(shù)列：f(n)=f(n-1)+f(n-2)
最大公約數(shù)：f(m, n) = f(n, m\%n)如果遞推公式不是很明確可以通過一個范式找到遞歸方法芒篷。首先明確函數(shù)功能是什么搜变，然后去找停止條件，最后利用這個函數(shù)在變化里找重復(fù)针炉，再在重復(fù)里找變化挠他，一般是不斷縮小參數(shù)的范圍。
注意這個參數(shù)有的時候需要額外傳入：
反轉(zhuǎn)字符串：
static String f(String myString, int begin) {
if (begin == myString.length()-1) {
return myString.charAt(begin)+"";
}
return f(myString, begin+1)+myString.charAt(begin);
}
在這里這個 begin 就是一個遞歸變量篡帕，如果不使用這個參數(shù)的話殖侵，還有一個辦法就是在遞歸過程中創(chuàng)建一個新的字符串（比原字符串少一個char），直接遞歸字符串镰烧，但是這樣的話就要創(chuàng)建很多額外的字符串拢军，占用大量的內(nèi)存。
另外需要注意遞歸問題的幾種形式怔鳖，第一種就是向上面例子一樣的單路徑的遞歸茉唉，或者是像漢諾塔或者斐波那契數(shù)列這種的雙分支遞歸，還有可能是類似于雙分支遞歸结执，但是會有判斷舍棄掉一半度陆，比如二分查找的遞歸寫法。
static void hano(int k, String from, String to, String help) {
if (k == 1) {
System.out.println("move "+k+" from "+from+" to "+to );
return;
}
hano(k-1, from, help, to);
System.out.println("move "+k+" from "+from+" to "+to );
hano(k-1, help, to, from);
}
private static int binerySearch(int[] arr, int low_index, int hight_index, int key){
if (low_index>hight_index) {
return -1;
}
int mind_index = (low_index+hight_index)>>>1;
int midVal = arr[mind_index];
if (midVal<key) {
return binerySearch(arr, mind_index+1, hight_index, key);
}
else if (midVal > key) {
return binerySearch(arr, low_index, mind_index-1, key);
}
else {
return mind_index;
}
}
