一、遞歸函數(shù)，通俗的說就是函數(shù)本身自己調(diào)用自己...
如:n!=n(n-1)!
你定義函數(shù)f(n)=nf(n-1)
而f(n-1)又是這個定義的函數(shù)。。這就是遞歸
二、為什么要用遞歸：遞歸的目的是簡化程序設(shè)計，使程序易讀
三、遞歸的弊端：雖然非遞歸函數(shù)效率高，但較難編程，可讀性較差。遞歸函數(shù)的缺點是增加了系統(tǒng)開銷，也就是說，每遞歸一次，棧內(nèi)存就多占用一截
四、遞歸的條件：需有完成任務(wù)的語句，需滿足遞歸的要求(減小而不是發(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.用遞歸函數(shù)算出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......（每一個數(shù)為前兩個數(shù)子之和，要求用遞歸函數(shù)）
用java遞歸來表示一個函數(shù):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用遞歸方法反向打印一個整數(shù)數(shù)組中的各個元素
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中遞歸函數(shù)的調(diào)用-求一個數(shù)的階乘
不考慮溢出：一般只能算到69的階乘……
注意：0的階乘0！=1
任何大于1的自然數(shù)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("輸入一個整數(shù)："); Scanner scan = new Scanner(System.in); int x = scan.nextInt(); int result = digui(x); System.out.println(result); } //遞歸函數(shù) public static int digui(int x){ if(x<=0){ return 1; }else{ return x*digui(x-1); } }}遞歸：一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。本案例很清楚的說明了遞歸是如何將一個復(fù)雜的問題轉(zhuǎn)化為規(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)); }}當函數(shù)被調(diào)用時，它的變量的空間是創(chuàng)建于運行時堆棧上的。以前調(diào)用的函數(shù)的變量扔保留在堆棧上，但他們被新函數(shù)的變量所掩蓋，因此 是不能被訪問的。
程序中的函數(shù)有兩個變量：參數(shù)n和局部變量factorial。下面的一些圖顯示了堆棧的狀態(tài)，當前可以訪問的變量位于棧頂。所有其他調(diào)用的變量飾以灰色的陰影，表示他們不能被當前正在執(zhí)行的函數(shù)訪問。
假定我們以5這個值調(diào)用遞歸函數(shù)。堆棧的內(nèi)容如下，棧頂位于最下方：
n multiply(n) factorial 5 multiply(5) 5*multiply(4) //第一次調(diào)用 4 multiply(4) 4*multiply(3) //第二次調(diào)用 3 multiply(3) 3*multiply(2) //第三次調(diào)用 2 multiply(2) 2*multiply(1) //第四次調(diào)用 1 multiply(1) 1 //第五次調(diào)用
從上面的信息可以很容易的看出，遞歸是如何將一個問題逐漸最小化來解決的，從方法調(diào)用開始，factorial結(jié)果都會被壓入棧，直到方法調(diào)用結(jié)束，最后從棧頂逐個返回得到結(jié)果。經(jīng)過逐個代入，結(jié)果如下:
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類型值進行比較，相等，則跳轉(zhuǎn)到位置9，這就是||的短路功能 5: iload_0 //此處是在第一個條件不成立的情況下執(zhí)行，從局部變量0中裝載int類型值（將n的值壓入棧） 6: ifne 14 //比較，如果不等于0則跳轉(zhuǎn)到位置14，注意：由于此處默認和0比較，所以沒有必要再將常量0壓入棧 9: iload_0 //如果在ifne處沒有跳轉(zhuǎn)，則從局部變量0中裝載int類型值（將n的值壓入棧） 10: istore_1 //將int類型值存入局部變量1中（彈出棧頂?shù)闹导淳植孔兞?壓入棧的值，再存入局部變量1中） 11: goto 23 //無條件跳轉(zhuǎn)至位置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，調(diào)用方法multiply 21: imul //執(zhí)行乘法操作，n * multiply(n - 1) 22: istore_1 //將int類型值存入局部變量1中，factorial=... 23: iload_1 //從局部變量1中裝載int類型值（將factorial的結(jié)果壓入棧） 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 } 新聞熱點
疑難解答
