1.什么是遞歸瘟檩？
程序調(diào)用自身的編程技巧稱為遞歸（ recursion）终佛，就好像你做了一個(gè)夢(mèng)，夢(mèng)里面夢(mèng)到夢(mèng)到自己又做了一個(gè)夢(mèng)翔忽，夢(mèng)中夢(mèng)英融。下面看一個(gè)例子：
public class JavaTest {
public static int method(int num) {
if (num > 1)
return num + method(num - 1);
else
return num;
}
public static void main(String[] args){
int sum =method(100);//從一加到一百的和
System.out.println(sum);
}
}
這樣遞歸的話呢，看上去代碼很簡潔歇式，但是遞歸是存在缺點(diǎn)的驶悟，就是在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)材失，因此遞歸次數(shù)過多容易造成棧溢出痕鳍。舉個(gè)栗子，就是打開一扇門，然后又進(jìn)去了一扇門笼呆，等到return的時(shí)候熊响，會(huì)從里向外一個(gè)一個(gè)的return，一個(gè)一個(gè)的出來诗赌，所以之前的這些“門”是占要地方的汗茄，遞歸層級(jí)過深就會(huì)造成堆棧溢出。那么怎么解決這個(gè)問題呢铭若？答案就是尾遞歸優(yōu)化洪碳。
2.什么是尾遞歸？
如果一個(gè)函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾叼屠，我們稱這個(gè)遞歸函數(shù)是尾遞歸的偶宫。當(dāng)遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達(dá)式的一部分時(shí)，這個(gè)遞歸調(diào)用就是尾遞歸环鲤。
public class JavaTest {
public static int method(int num,int sum) {
if (num > 1) {
sum += num;
return method(num - 1,sum);
}
else {
return sum+1;
}
}
public static int method(int num) {
return method(num,0);
}
public static void main(String[] args){
int sum =method(100);
System.out.println(sum);
}
}
如上纯趋，使用了一個(gè)變量sum保存了遞歸調(diào)用的結(jié)果，并傳到下一次遞歸調(diào)用中冷离，這就是尾遞歸吵冒。到遞歸的結(jié)尾的時(shí)候，就可以直接return西剥，不需要一層一層的出來痹栖。這樣的話，就不用保存前面那些函數(shù)的堆棧瞭空，也就不會(huì)堆棧溢出了揪阿。
3.編譯器的優(yōu)化
雖然手寫成了尾遞歸的形式，但是編譯成字節(jié)碼的時(shí)候咆畏，優(yōu)不優(yōu)化得看編譯器的心情南捂，所以很蛋疼。編譯器如果支持尾遞歸優(yōu)化旧找，那么就會(huì)利用尾遞歸特點(diǎn)來進(jìn)行優(yōu)化溺健，在遞歸調(diào)用的時(shí)候重復(fù)使用同一個(gè)函數(shù)棧幀，效率很高钮蛛，however鞭缭，java還沒有實(shí)現(xiàn)尾遞歸優(yōu)化的支持，官方是推薦使用循環(huán)魏颓，迭代岭辣，不使用遞歸。
