Java语言程序设计（十四）递归算法应用实例，以及数组的复制，传递，返回

1.数组的复制

在程序中，经常需要复制一个数组或数组的一部分，这种情况下，我们首先想到的可能是会尝试使用赋值语句：list1=list2;不过这种语句并不能将list1引用的数组内容复制给list2，而只是将list1的引用值复制给了list2，在这条语句过后，list1和list2都指向了同一个数组，list2原先引用的数组会被自动收回。

Java中，可以使用赋值语句复制基本数据类型的变量，但是不能复制数组，将一个数组变量赋值给另一个数组变量，实际上是引用的复制，使两个变量都指向相同的内存地址。

复制数组有三种方法：

（1）使用循环语句逐个复制数组的元素。

（2）使用System类中的静态方法arraycopy。

（3）使用clone方法复制，这个我们会在后面的文章中介绍。

我们可以使用循环将源数组中的每个元素复制到目标数组中的对应元素，下面举个例子，使用for循环将sourceArray复制到targetArray：

int[]sourceArray ={2,1,5,4,8};

int[]targetArray = new int[sourceArray.length];

for(int i=0;i<sourceArray.length;i++){

targetArray[i] = sourceArray[i];

}

另一种方法是使用java.lang.System类的arraycopy方法复制数组，而不是使用循环，arrarcopy的语法如下：

arraycopy(sourceArray,src_pos,targetArray,tar_pos,length);

其中，参数src_pos和tar_pos分别表示在源数组sourceArray和目标数组targetArray中的起始位置，复制的元素个数由参数length指定，我们举一个例子来看：

System.arraycopy(sourceArray,0,targetArray,0,sourceArray.length);

2.给方法传递数组

正如前面给方法传递基本数据一样，也可以给方法传递数组，我们可以通过传递一个数组调用printArray方法来显示。

3.从方法中返回数组

我们可以在调用方法时向方法传递一个数组，方法也可以返回一个数组，例如，下面的方法返回一个与输入数组顺序相反的数组：

public static int[] reverse(int[] list){

int[] result = new int[list.length];

for(int i=0,j=result.length-1;i<list.length;i++,j–){

result[j]=list[i];

}

return result;

}

4.递归算法

什么叫做递归？一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，递归函数就是直接或间接调用自身的函数，也就是自身调用自己。那我们一般什么时候使用递归呢？

递归是常用的编程技术，其基本思想就是“自己调用自己”，一个使用递归技术的方法即是直接或间接的调用自身的方法。递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想，它可以用简单的程序来解决某些复杂的计算问题，但是运算量较大。
还有些数据结构如二叉树，结构本身固有递归特性；此外，有一类问题，其本身没有明显的递归结构，但用递归程序求解比其他方法更容易编写程序，如八皇后问题、汉诺塔问题等。

正因为递归程序的普遍性，我们应该学会使用递归来求解问题。直接递归程序与间接递归中都要实现当前层调用下一层时的参数传递，并取得下一层所返回的结果，并向上一层调用返回当前层的结果。至于各层调用中现场的保存与恢复，均由程序自动实现，不需要人工干预。因此，在递归程序的设计中关键是找出调用所需要的参数、返回的结果及递归调用结束的条件。

我们现在举一个Java应用实例来应用一下递归算法，比如说正整数的划分数这种问题，例如3可以分解为3 2+1和1+1+1，4可以分解为 4 3+1，2+2，2+1+1，1+1+1+1，6可以分解为 6 5+1，4+2，4+1+1，3+3，3+2+1，3+1+1+1，2+2+2，2+2+1+1，2+1+1+1+1，1+1+1+1+1+1，因此设立一个q（n，m）意义为，将n正整数划分，m为限定，最大的划分数不能大于m，我们可以建立如下的递归关系：

q(n,m)=1——-n=1,m=1

q(n,m)=q(n,n)——n<m

q(n,m)= 1+q(m,m-1)——n=m

q(n,m)=q(n,m-1)+q(n-m,m)——n>m>1

程序清单如下：

package digui;

import java.util.Scanner;

/**
*
* @author john
*/
public class Digui {
public static int q(int n, int m){
  if (m<0 || n<0){
   return 0;
  }
  else if (m == 1 || n == 1){
   return 1;
  }
  else if (n<m){
   return q(n, n);
  }
  else if (n == m){
   return 1 + q(n, n – 1);
  }
  else{
   return q(n, m – 1) + q(n – m, m);
  }
}
public static void main(String[] args) {
  System.out.print(\”Please input n\\n\”);
  Scanner input=new Scanner(System.in);
  int n=input.nextInt();
  System.out.print(\”Please input m\\n\”);
  int m=input.nextInt();
  int s = q(n, m);
  System.out.print(s);
}