快捷導(dǎo)航

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

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

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

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

遞歸的三個條件：
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ù)調(diào)用自身；
(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ù)列的遞歸算法 
 *輸入?yún)?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)); 
  } 
 } 
  
 /** 
 *方法描述：主方法 
 *輸入?yún)?shù)：String[] args 
 *返回類型：void 
 */ 
 public static void main(String[] args) 
 { 
 System.out.println(fun(10)); 
 } 
}

運行結(jié)果如下所示：

復(fù)制代碼代碼如下:

55

您可能感興趣的文章: