Java使用遞歸解決算法問題的實例講解

更新時間：2016年06月13日 09:00:33 作者：it_wangxiangpan

遞歸算法的實質是把問題分解成規(guī)?？s小的同類問題的子問題,然后遞歸調用方法來表示問題的解,這里我們就來看幾個Java使用遞歸解決算法問題的實例講解

解釋：程序調用自身的編程技巧叫做遞歸。
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。一個過程或函數(shù)在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。

遞歸的三個條件：
1.邊界條件
2.遞歸前進段
3.遞歸返回段

當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

下面通過兩個示例程序來說明：
1.使用Java代碼求5的階乘。（5的階乘=5*4*3*2*1）

package org.wxp.recursion; 
/** 
 * 計算5的階乘(result = 5*4*3*2*1) 
 * @author Champion.Wong 
 */ 
public class Test01 { 
 public static void main(String[] args) { 
  System.out.println(f(5)); 
 } 
  
 public static int f(int n) { 
  if (1 == n) 
   return 1; 
  else 
   return n*(n-1); 
 } 
}

此題中，按照遞歸的三個條件來分析：
(1)邊界條件：階乘，乘到最后一個數(shù)，即1的時候，返回1，程序執(zhí)行到底；
(2)遞歸前進段：當前的參數(shù)不等于1的時候，繼續(xù)調用自身；
(3)遞歸返回段：從最大的數(shù)開始乘，如果當前參數(shù)是5，那么就是5*4，即5*(5-1)，即n*(n-1)

2.使用Java代碼求數(shù)列：1，1，2，3，5，8......第40位的數(shù)

package org.wxp.recursion;  
/** 
 * 求數(shù)列：1，1，2，3，5，8......第40位的數(shù) 
 */ 
public class Test_02_Fibonacci { 
  public static void main(String[] args) { 
    System.out.println(f(6)); 
  } 
   
  public static int f(int n ) { 
    if (1== n || 2 == n)  
      return 1; 
    else 
      return f(n-1) + f(n-2); 
  } 
}

3.問題描述：求解Fibonacci數(shù)列的第10個位置的值？ （斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*））
程序清單：

/** 
 *<p>Title:Java遞歸算法實例</p> 
 *<p>Description:利用遞歸算法求解Fibonacci數(shù)列第5個數(shù)的值</p> 
 *<p>Filename:Fibonacci.java</p> 
 */ 
public class Fibonacci 
{ 
 /** 
 *方法描述：求解Fibonacci數(shù)列的遞歸算法 
 *輸入參數(shù)：int n 
 *返回類型：int 
 */ 
 public static int fun(int n) 
 { 
  if(1==n || 2==n) 
  { 
  return 1; 
  } 
  else  
  { 
  return (fun(n-1) + fun(n-2)); 
  } 
 } 
  
 /** 
 *方法描述：主方法 
 *輸入參數(shù)：String[] args 
 *返回類型：void 
 */ 
 public static void main(String[] args) 
 { 
 System.out.println(fun(10)); 
 } 
}

運行結果如下所示：

復制代碼代碼如下:

55

您可能感興趣的文章: