Java使用递归解决算法问题的实例讲解

解释：程序调用自身的编程技巧叫做递归。
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

递归的三个条件：
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)边界条件：阶乘，乘到最后一个数，即1的时候，返回1，程序执行到底；
(2)递归前进段：当前的参数不等于1的时候，继续调用自身；
(3)递归返回段：从最大的数开始乘，如果当前参数是5，那么就是5*4，即5*(5-1)，即n*(n-1)

2.使用Java代码求数列：1，1，2，3，5，8......第40位的数

package org.wxp.recursion;  
/** 
 * 求数列：1，1，2，3，5，8......第40位的数 
 */ 
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数列的第10个位置的值？ （斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*））
程序清单：

/** 
 *<p>Title:Java递归算法实例</p> 
 *<p>Description:利用递归算法求解Fibonacci数列第5个数的值</p> 
 *<p>Filename:Fibonacci.java</p> 
 */ 
public class Fibonacci 
{ 
 /** 
 *方法描述：求解Fibonacci数列的递归算法 
 *输入参数：int n 
 *返回类型：int 
 */ 
 public static int fun(int n) 
 { 
  if(1==n || 2==n) 
  { 
  return 1; 
  } 
  else  
  { 
  return (fun(n-1) + fun(n-2)); 
  } 
 } 
  
 /** 
 *方法描述：主方法 
 *输入参数：String[] args 
 *返回类型：void 
 */ 
 public static void main(String[] args) 
 { 
 System.out.println(fun(10)); 
 } 
} 

运行结果如下所示：

55