靖江市屬于哪里有做網(wǎng)站的網(wǎng)絡(luò)銷售這個工作到底怎么樣
遞歸方法調(diào)用 :方法自己調(diào)用自己的現(xiàn)象就稱為遞歸。
遞歸的分類 : 直接遞歸、間接遞歸。
?直接遞歸:方法自身調(diào)用自己
public void methodA (){methodA ();}
間接遞歸:可以理解為A()方法調(diào)用B()方法,B()方法調(diào)用C()方法,C()方法調(diào)用A()方法。?
public static void A (){B ();}public static void B (){C ();}public static void C (){A ();}
說明 :
遞歸方法包含了一種 隱式的循環(huán) 。
遞歸方法會 重復(fù)執(zhí)行 某段代碼,但這種重復(fù)執(zhí)行無須循環(huán)控制。
遞歸一定要向 已知方向 遞歸,否則這種遞歸就變成了無窮遞歸,停不下來,類似于 死循環(huán) 。最終
發(fā)生 棧內(nèi)存溢出 。
舉例1:計算1 ~ n的和
public class RecursionDemo {public static void main ( String [] args ) {RecursionDemo demo = new RecursionDemo ();// 計算 1~num 的和,使用遞歸完成int num = 5 ;// 調(diào)用求和的方法int sum = demo . getSum ( num );// 輸出結(jié)果System . out . println ( sum );}/*通過遞歸算法實現(xiàn) .參數(shù)列表 :int返回值類型 : int*/public int getSum ( int num ) {/*num 為 1 時 , 方法返回 1,相當(dāng)于是方法的出口 ,num 總有是 1 的情況*/if ( num == 1 ){return 1 ;}/*num 不為 1 時 , 方法返回 num +(num-1) 的累和遞歸調(diào)用 getSum 方法*/return num + getSum ( num - 1 );}}
代碼執(zhí)行圖解:
代碼解釋
/* * 當(dāng)程序執(zhí)行時,它會按照以下流程進(jìn)行:1. `main` 方法被調(diào)用。 2. 一個 `RecursionDemo` 類的對象 `demo` 被創(chuàng)建。 3. `n` 被賦值為 5。 4. 調(diào)用 `demo.getSum(n)` 方法,其中 `n` 的值為 5。 5. 進(jìn)入 `getSum` 方法。 6. `n` 的值不為 1,因此程序執(zhí)行 `return n + getSum(n - 1);`,其中 `n - 1` 的值為 4。 7. 程序遞歸調(diào)用 `getSum` 方法,將參數(shù)值 `4` 傳遞給它。 8. 再次進(jìn)入 `getSum` 方法。 9. `n` 的值不為 1,因此程序執(zhí)行 `return n + getSum(n - 1);`,其中 `n - 1` 的值為 3。 10. 程序遞歸調(diào)用 `getSum` 方法,將參數(shù)值 `3` 傳遞給它。 11. 再次進(jìn)入 `getSum` 方法。 12. `n` 的值不為 1,因此程序執(zhí)行 `return n + getSum(n - 1);`,其中 `n - 1` 的值為 2。 13. 程序遞歸調(diào)用 `getSum` 方法,將參數(shù)值 `2` 傳遞給它。 14. 再次進(jìn)入 `getSum` 方法。 15. `n` 的值不為 1,因此程序執(zhí)行 `return n + getSum(n - 1);`,其中 `n - 1` 的值為 1。 16. 程序遞歸調(diào)用 `getSum` 方法,將參數(shù)值 `1` 傳遞給它。 17. 再次進(jìn)入 `getSum` 方法。 18. `n` 的值為 1,因此程序直接返回 1。 19. 回到上一層遞歸調(diào)用,將返回的值 1 加上當(dāng)前層的 `n` 的值(為 2),得到結(jié)果 3,返回給上一層。 20. 繼續(xù)返回上一層遞歸調(diào)用,將返回的值 3 加上當(dāng)前層的 `n` 的值(為 3),得到結(jié)果 6,返回給上一層。 21. 繼續(xù)返回上一層遞歸調(diào)用,將返回的值 6 加上當(dāng)前層的 `n` 的值(為 4),得到結(jié)果 10,返回給上一層。 22. 繼續(xù)返回上一層遞歸調(diào)用,將返回的值 10 加上當(dāng)前層的 `n` 的值(為 5),得到結(jié)果 15,返回給上一層。 23. 回到 `main` 方法,將返回的結(jié)果 15 賦值給 `sum` 變量。 24. `System.out.println(sum);` 將結(jié)果打印到控制臺上。所以,程序的輸出結(jié)果為 `15`。 * * * * */ }
舉例2:遞歸方法計算n!
public int multiply ( int num ){if ( num == 1 ){return 1 ;} else {return num * multiply ( num - 1 );}}
?
public int f ( int num ){if ( num == 0 ){return 1 ;} else if ( num == 1 ){return 4 ;} else {return 2 * f ( num - 1 ) + f ( num - 2 );}}
舉例3:已知有一個數(shù)列:f(0) = 1,f(1) = 4,f(n+2)=2*f(n+1) + f(n),其中n是大于0的整數(shù),求f(10)的值。
public int func ( int num ){if ( num == 20 ){return 1 ;} else if ( num == 21 ){return 4 ;} else {return func ( num + 2 ) - 2 * func ( num + 1 );}}
舉例4:計算斐波那契數(shù)列(Fibonacci)的第n個值
斐波那契數(shù)列滿足如下規(guī)律,
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 ,....
即從第三個數(shù)開始,一個數(shù)等于前兩個數(shù)之和。假設(shè) f(n) 代表斐波那契數(shù)列的第 n 個值,那么 f(n) 滿足:
f(n) = f(n-2) + f(n-1);
// 使用遞歸的寫法int f ( int n ) { // 計算斐波那契數(shù)列第 n 個值是多少if ( n < 1 ) { // 負(fù)數(shù)是返回特殊值 1 ,表示不計算負(fù)數(shù)情況return 1 ;}if ( n == 1 || n == 2 ) {return 1 ;}return f ( n - 2 ) + f ( n - 1 );}// 不用遞歸int fValue ( int n ) { // 計算斐波那契數(shù)列第 n 個值是多少if ( n < 1 ) { // 負(fù)數(shù)是返回特殊值 1 ,表示不計算負(fù)數(shù)情況return 1 ;}if ( n == 1 || n == 2 ) {return 1 ;}// 從第三個數(shù)開始, 等于 前兩個整數(shù)相加int beforeBefore = 1 ; // 相當(dāng)于 n=1 時的值int before = 1 ; // 相當(dāng)于 n=2 時的值int current = beforeBefore + before ; // 相當(dāng)于 n=3 的值// 再完后for ( int i = 4 ; i <= n ; i ++ ) {beforeBefore = before ;before = current ;current = beforeBefore + before ;/* 假設(shè) i=4beforeBefore = before; // 相當(dāng)于 n=2 時的值before = current; // 相當(dāng)于 n=3 的值current = beforeBefore + before; // 相當(dāng)于 n = 4 的值假設(shè) i=5beforeBefore = before; // 相當(dāng)于 n=3 的值before = current; // 相當(dāng)于 n = 4 的值current = beforeBefore + before; // 相當(dāng)于 n = 5 的值....*/}return current ;}
舉例5:面試題
宋老師,我今天去百度面試,遇到一個一個雙重遞歸調(diào)用的問題,我琢磨了一下,完全不知道為什
么。打斷點了,也還是沒看懂為什么程序會那樣走。您有空可以看一下,求指教。

private int count = 0 ;public int recursion ( int k ) {count ++ ;System . out . println ( "count1:" + count + " k:" + k );if ( k <= 0 ) {return 0 ;}return recursion ( k - 1 ) + recursion ( k - 2 ); //287//return recursion(k - 1);//11//return recursion(k - 1) + recursion(k - 1);//2047}
剖析:
最后說兩句:1. 遞歸調(diào)用會占用大量的系統(tǒng)堆棧,內(nèi)存耗用多,在遞歸調(diào)用層次多時速度要比循環(huán) 慢的多 ,所以在使用遞歸時要慎重。2. 在要求高性能的情況下盡量避免使用遞歸,遞歸調(diào)用既花時間又 耗內(nèi)存 ??紤]使用循環(huán)迭 代。