java 遞歸深入理解

更新時(shí)間：2012年11月26日 11:08:14 投稿：whsnow

一個(gè)過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解,需要的朋友可以參考下

一、遞歸函數(shù)，通俗的說就是函數(shù)本身自己調(diào)用自己...

如:n!=n(n-1)!
你定義函數(shù)f(n)=nf(n-1)

而f(n-1)又是這個(gè)定義的函數(shù)。。這就是遞歸

二、為什么要用遞歸：遞歸的目的是簡化程序設(shè)計(jì)，使程序易讀

三、遞歸的弊端：雖然非遞歸函數(shù)效率高，但較難編程，可讀性較差。遞歸函數(shù)的缺點(diǎn)是增加了系統(tǒng)開銷，也就是說，每遞歸一次，棧內(nèi)存就多占用一截

四、遞歸的條件：需有完成任務(wù)的語句，需滿足遞歸的要求(減小而不是發(fā)散)

五、遞歸進(jìn)階：
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.要求輸出一個(gè)序列：1,1,2,3,5,8,11......（每一個(gè)數(shù)為前兩個(gè)數(shù)子之和，要求用遞歸函數(shù)）
用java遞歸來表示一個(gè)函數(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用遞歸方法反向打印一個(gè)整數(shù)數(shù)組中的各個(gè)元素

  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.編程求解：若一頭小母牛，從出生起第四個(gè)年頭開始每年生一頭母牛，按次規(guī)律，第 n 年時(shí)有多少頭母牛？

  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)用-求一個(gè)數(shù)的階乘

不考慮溢出：一般只能算到69的階乘……

注意：0的階乘0！=1

任何大于1的自然數(shù)n階乘表示方法：
n!=1×2×3×……×n
或n!=n×(n-1)!
搜索0的階乘，可以出來一個(gè)在線計(jì)算器，很實(shí)用哦?。?/p>

package test;

import java.util.Scanner;

public class DiGui {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("輸入一個(gè)整數(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);
		}
	}
}

遞歸：一個(gè)過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。本案例很清楚的說明了遞歸是如何將一個(gè)復(fù)雜的問題轉(zhuǎn)化為規(guī)模較小的問題來解決的。下面通過一個(gè)小例子來說明遞歸的原理。

/**
* @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));
  }
}

當(dāng)函數(shù)被調(diào)用時(shí)，它的變量的空間是創(chuàng)建于運(yùn)行時(shí)堆棧上的。以前調(diào)用的函數(shù)的變量扔保留在堆棧上，但他們被新函數(shù)的變量所掩蓋，因此是不能被訪問的。
程序中的函數(shù)有兩個(gè)變量：參數(shù)n和局部變量factorial。下面的一些圖顯示了堆棧的狀態(tài)，當(dāng)前可以訪問的變量位于棧頂。所有其他調(diào)用的變量飾以灰色的陰影，表示他們不能被當(dāng)前正在執(zhí)行的函數(shù)訪問。
假定我們以5這個(gè)值調(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)用

從上面的信息可以很容易的看出，遞歸是如何將一個(gè)問題逐漸最小化來解決的，從方法調(diào)用開始，factorial結(jié)果都會(huì)被壓入棧，直到方法調(diào)用結(jié)束，最后從棧頂逐個(gè)返回得到結(jié)果。經(jīng)過逐個(gè)代入，結(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
注意：因?yàn)閙ultiply(1)或multiply(0)返回的值為1
所以就有 2*multiply(1)=2*1=2
又因?yàn)閙ultiply(2)符合遞歸條件，遞歸后可化為2*multiply(1)
所以就有3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
因?yàn)閙ultiply(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 //將兩個(gè)int類型值進(jìn)行比較，相等，則跳轉(zhuǎn)到位置9，這就是||的短路功能 
5: iload_0 //此處是在第一個(gè)條件不成立的情況下執(zhí)行，從局部變量0中裝載int類型值（將n的值壓入棧） 
6: ifne 14 //比較，如果不等于0則跳轉(zhuǎn)到位置14，注意：由于此處默認(rèn)和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 
}

您可能感興趣的文章: