一、遞歸函數，通俗的說就是函數本身自己調用自己...
如:n!=n(n-1)!
你定義函數f(n)=nf(n-1)
而f(n-1)又是這個定義的函數。。這就是遞歸
二、為什么要用遞歸：遞歸的目的是簡化程序設計，使程序易讀
三、遞歸的弊端：雖然非遞歸函數效率高，但較難編程，可讀性較差。遞歸函數的缺點是增加了系統(tǒng)開銷，也就是說，每遞歸一次，棧內存就多占用一截
四、遞歸的條件：需有完成任務的語句，需滿足遞歸的要求(減小而不是發(fā)散)
五、遞歸進階：
1.用遞歸算n的階乘：
分析：n!=n*(n-1)*(n-2)...*1
public int dReturn(int n){ if(n==1){ return 1; }else{ return n*dReturn(n-1); } } 2.用遞歸函數算出1到n的累加：1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1; }else{ return n+dReturn(n-1); } } 3.要求輸出一個序列：1,1,2,3,5,8,11......（每一個數為前兩個數子之和，要求用遞歸函數）
用java遞歸來表示一個函數:F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
分析：X1=1; X2=1; X3=X1+X2; X4=X2+X3; ... ; Xn=X(n-1)+X(n-2)
public int F(int n){ if(n==1){ return 1; }else if(n==2){ return 1; }else{ return F(n-1)+F(n-2); } } 4.java用遞歸方法反向打印一個整數數組中的各個元素
public static void printAll(int index,int[] arr){ System.out.println(arr[index]); if(index > 0){ printAll(--index,arr); } } public static void main(String[] args){ int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr); } 5.編程求解：若一頭小母牛，從出生起第四個年頭開始每年生一頭母牛，按次規(guī)律，第 n 年時有多少頭母牛？
public static int cattle(int n){ if(n<=0){ return 0; }else if(n<=3){ return 1; }else{ return cattle(n-1)+cattle(n-3); } } public static void main(String[] args){ int n=10; System.out.println(n+"年后共有"+cattle(n)+"頭牛"); } 遞歸、線性遞歸、尾遞歸的概念？
Java中遞歸函數的調用-求一個數的階乘
不考慮溢出：一般只能算到69的階乘……
注意：0的階乘0！=1
任何大于1的自然數n階乘表示方法：
n!=1×2×3×……×n
或n!=n×(n-1)!
搜索0的階乘，可以出來一個在線計算器，很實用哦！！
package test;import java.util.Scanner;public class DiGui { public static void main(String[] args) { // TODO Auto-generated method stub System.out.println("輸入一個整數："); Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int result = digui(x); System.out.println(result); } //遞歸函數 public static int digui(int x){ if(x<=0){ return 1; }else{ return x*digui(x-1); } }}遞歸：一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解。本案例很清楚的說明了遞歸是如何將一個復雜的問題轉化為規(guī)模較小的問題來解決的。下面通過一個小例子來說明遞歸的原理。
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/public class Test { static int multiply(int n) { int factorial; // ?? if ((n == 1) || (n == 0)) { factorial = n; } else { factorial = n * multiply(n - 1); } return factorial; } public static void main(String[] args) { System.out.println(multiply(5)); }}當函數被調用時，它的變量的空間是創(chuàng)建于運行時堆棧上的。以前調用的函數的變量扔保留在堆棧上，但他們被新函數的變量所掩蓋，因此 是不能被訪問的。
程序中的函數有兩個變量：參數n和局部變量factorial。下面的一些圖顯示了堆棧的狀態(tài)，當前可以訪問的變量位于棧頂。所有其他調用的變量飾以灰色的陰影，表示他們不能被當前正在執(zhí)行的函數訪問。
假定我們以5這個值調用遞歸函數。堆棧的內容如下，棧頂位于最下方：
n multiply(n) factorial 5 multiply(5) 5*multiply(4) //第一次調用 4 multiply(4) 4*multiply(3) //第二次調用 3 multiply(3) 3*multiply(2) //第三次調用 2 multiply(2) 2*multiply(1) //第四次調用 1 multiply(1) 1 //第五次調用
從上面的信息可以很容易的看出，遞歸是如何將一個問題逐漸最小化來解決的，從方法調用開始，factorial結果都會被壓入棧，直到方法調用結束，最后從棧頂逐個返回得到結果。經過逐個代入，結果如下:
n=1 1 向上返回 1
n=2 2*multiply(1) 向上返回 2*1=2
n=3 3*multiply(2) 向上返回 3*(2*1)=6
n=4 4*multiply(3) 向上返回 4*(3*(2*1))=24
n=5 5*multiply(4) 向上返回 5*(4*(3*(2*1)))=120
注意：因為multiply(1)或multiply(0)返回的值為1
所以就有 2*multiply(1)=2*1=2
又因為multiply(2)符合遞歸條件，遞歸后可化為2*multiply(1)
所以就有3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
因為multiply(3)遞歸后可化為3*multiply(2)
所以multiply(4)=4*multiply(3)=4*(3*multiply(2))=4*(3*(2*1))=24
以此類推，multiply(5)=5*multiply(4)
可化為5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120
再來看看字節(jié)碼信息:
public class Test extends java.lang.Object{ public Test(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/Object."<init>":()V 4: return static int multiply(int); Code: 0: iload_0 1: iconst_1 //將int類型常量1壓入棧 2: if_icmpeq 9 //將兩個int類型值進行比較，相等，則跳轉到位置9，這就是||的短路功能 5: iload_0 //此處是在第一個條件不成立的情況下執(zhí)行，從局部變量0中裝載int類型值（將n的值壓入棧） 6: ifne 14 //比較，如果不等于0則跳轉到位置14，注意：由于此處默認和0比較，所以沒有必要再將常量0壓入棧 9: iload_0 //如果在ifne處沒有跳轉，則從局部變量0中裝載int類型值（將n的值壓入棧） 10: istore_1 //將int類型值存入局部變量1中（彈出棧頂的值即局部變量0壓入棧的值，再存入局部變量1中） 11: goto 23 //無條件跳轉至位置23 14: iload_0 //位置6處的比較，如果不等于0執(zhí)行此指令，從局部變量0中裝載int類型值（將n的值壓入棧） 15: iload_0 //從局部變量0中裝載int類型值（將n的值壓入棧） 16: iconst_1 //將int類型常量1壓入棧，常量1是代碼中n-1的1 17: isub //執(zhí)行減法操作，n-1 18: invokestatic #2; //Method multiply:(I)I，調用方法multiply 21: imul //執(zhí)行乘法操作，n * multiply(n - 1) 22: istore_1 //將int類型值存入局部變量1中，factorial=... 23: iload_1 //從局部變量1中裝載int類型值（將factorial的結果壓入棧） 24: ireturn //方法返回 public static void main(java.lang.String[]); Code: 0: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream; 3: iconst_5 4: invokestatic #2; //Method multiply:(I)I 7: invokevirtual #4; //Method java/io/PrintStream.println:(I)V 10: return } 新聞熱點
疑難解答
