递归算法java代码实现 递归算法一般用什么实现

用java递归方法实现

1、递归做为一种算法在程序设计语言中广泛使用，是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。

富拉尔基网站建设公司创新互联,富拉尔基网站设计制作，有大型网站制作公司丰富经验。已为富拉尔基近千家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱，请找那个售后服务好的富拉尔基做网站的公司定做！

2、递归算法一般用于解决三类问题：

1）数据的定义是按递归定义的。（Fibonacci（斐波那契）的函数）

2）问题解法按递归算法实现。（回溯）

3）数据的结构形式是按递归定义的。（树的遍历，图的搜索）

java递归算法

1.汉诺塔问题

import javax.swing.JOptionPane;

public class Hanoi {

private static final String DISK_B = "diskB";

private static final String DISK_C = "diskC";

private static final String DISK_A = "diskA";

static String from=DISK_A;

static String to=DISK_C;

static String mid=DISK_B;

public static void main(String[] args) {

String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");

int num=Integer.parseInt(input);

move(num，from，mid，to);

}

private static void move(int num， String from2， String mid2， String to2) {

if(num==1){

System.out.println("move disk 1 from "+from2+" to "+to2);

}

else {

move(num-1，from2，to2，mid2);

System.out.println("move disk "+num+" from "+from2+" to "+to2);

move(num-1，mid2，from2，to2);

}

}

}

2. 这是一个排列的例子，它所做的工作是将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc" 则程序会输出：

abc

acb

bac

bca

cab

cba

(1)算法的出口在于：low=high也就是现在给出的排列元素只有一个时。

(2)算法的逼近过程：先确定排列的第一位元素，也就是循环中i所代表的元素，

然后low+1开始减少排列元素，如此下去，直到low=high

public static void permute(String str) {

char[] strArray = str.toCharArray();

permute(strArray， 0， strArray.length - 1);

}

public static void permute(char[] list， int low， int high) {

int i;

if (low == high) {

String cout = "";

for (i = 0; i = high; i++)

cout += list[i];

System.out.println(cout);

} else {

for (i = low; i = high; i++) {

char temp = list[low];

list[low] = list[i];

list[i] = temp;

permute(list， low + 1， high);

temp = list[low];

list[low] = list[i];

list[i] = temp;

}

}

}

3。这是一个组合的例子，与上述的例子相似，只是它所做的工作是，输出所给字符串中制定数目的元素的组合种类

(1)程序出口在于n=1，此时只要输出目标数组的所有元素即可

(2)逼近过程，当n1　的时候，我们先取第一个元素放入目标数组中，然后n-1，如此下去，最后出来。

import javax.swing.JOptionPane;

public class Combination {

/**

* @param args

*/

public static void main(String[] args) {

String input = JOptionPane.showInputDialog("please input your String： ");

String numString = JOptionPane.showInputDialog("please input the number of your Combination： ");

int num = Integer.parseInt(numString);

Combine(input， num);

}

private static void Combine(String input， int num) {

char[] a = input.toCharArray();

String b = "";

Combine(a， num， b， 0， a.length);

}

private static void Combine(char[] a， int num， String b， int low， int high) {

if (num == 0) {

System.out.println(b);

} else {

for (int i = low; i a.length; i++) {

b += a[i];

Combine(a， num - 1， b， i+1， a.length);

b=b.substring(0， b.length()-1);

}

}

}

}

java二分法查找的递归算法怎么实现

什么是二分查找？

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找优缺点

优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

使用条件：查找序列是顺序结构，有序。

过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

利用循环的方式实现二分法查找

public class BinarySearch {

public static void main(String[] args) {

// 生成一个随机数组        int[] array = suiji();

// 对随机数组排序        Arrays.sort(array);

System.out.println("产生的随机数组为： " + Arrays.toString(array));

System.out.println("要进行查找的值： ");

Scanner input = new Scanner(System.in);

// 进行查找的目标值        int aim = input.nextInt();

// 使用二分法查找        int index = binarySearch(array, aim);

System.out.println("查找的值的索引位置： " + index);

}

/**     * 生成一个随机数组     *

* @return 返回值，返回一个随机数组     */

private static int[] suiji() {

// random.nextInt(n)+m  返回m到m+n-1之间的随机数        int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循环遍历为数组赋值        for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/**     * 二分法查找  ---循环的方式实现     *

* @param array 要查找的数组     * @param aim 要查找的值     * @return 返回值，成功返回索引，失败返回-1     */

private static int binarySearch(int[] array, int aim) {

// 数组最小索引值        int left = 0;

// 数组最大索引值        int right = array.length - 1;

int mid;

while (left = right) {

mid = (left + right) / 2;

// 若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围            if (aim array[mid]) {

right = mid - 1;

// 若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围            } else if (aim array[mid]) {

left = mid + 1;

// 若查找数据与中间元素值正好相等，则放回中间元素值的索引            } else {

return mid;

}

}

return -1;

}}

运行结果演示：

由以上运行结果我们得知，如果要查找的数据在数组中存在，则输出该数据在数组中的索引；如果不存在则输出 -1 ，也就是打印 -1 则该数在数组中不存在，反之则存在。

四、利用递归的方式实现二分法查找

public class BinarySearch2 {

public static void main(String[] args) {

// 生成一个随机数组        int[] array = suiji();

// 对随机数组排序        Arrays.sort(array);

System.out.println("产生的随机数组为： " + Arrays.toString(array));

System.out.println("要进行查找的值： ");

Scanner input = new Scanner(System.in);

// 进行查找的目标值        int aim = input.nextInt();

// 使用二分法查找        int index = binarySearch(array, aim, 0, array.length - 1);

System.out.println("查找的值的索引位置： " + index);

}

/**     * 生成一个随机数组     *     * @return 返回值，返回一个随机数组     */

private static int[] suiji() {

// Random.nextInt(n)+m  返回m到m+n-1之间的随机数        int n = new Random().nextInt(6) + 5;

int[] array = new int[n];

// 循环遍历为数组赋值        for (int i = 0; i array.length; i++) {

array[i] = new Random().nextInt(100);

}

return array;

}

/**     * 二分法查找 ---递归的方式     *     * @param array 要查找的数组     * @param aim   要查找的值     * @param left  左边最小值     * @param right 右边最大值     * @return 返回值，成功返回索引，失败返回-1     */

private static int binarySearch(int[] array, int aim, int left, int right) {

if (aim array[left] || aim array[right]) {

return -1;

}

// 找中间值        int mid = (left + right) / 2;

if (array[mid] == aim) {

return mid;

} else if (array[mid] aim) {

//如果中间值大于要找的值则从左边一半继续递归            return binarySearch(array, aim, left, mid - 1);

} else {

//如果中间值小于要找的值则从右边一半继续递归            return binarySearch(array, aim, mid + 1, array.length-1);

}

}}

运行结果演示：

总结：

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。通常我们如果使用循环实现代码只要不是太繁琐都选择循环的方式实现~

用java递归算法求一个数字的阶乘

1、采用自顶向上的递归方法，代码如下：

import java.util.Scanner;

public class Test {

@SuppressWarnings("resource")

public static void main(String[] args) {

// 从控制台输入一个整数

Scanner in = new Scanner(System.in);

int b = in.nextInt();

// 声明一个Test对象，调用cal方法获得结果

Test test = new Test();

long a = test.cal(b);

System.out.println(a);

}

// 通过递归掉调用最终返回结果

public long cal(int number) {

// 如果数字为1，则直接返回

if (number == 1) {

return 1;

} else {// 否则递归求值

return number * cal(number - 1);

}

}

}

2、递归方法：

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

3、特点：

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

java递归算法的例子。

阶乘：

要求：给定一个数值，计算出它的阶乘值，例如5的阶乘为5*4*3*2*1

实现：

[html] view plaincopy

span style="font-size:12px;"  // 利用递归实现一个数的阶乘值      private static BigDecimal getNum(BigDecimal inNum) {          if (inNum.compareTo(BigDecimal.ONE) == 0) {              return inNum;          }          return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE)));      }/span

（2）Fibonacci数列：1，1，2，3，5，8，13……

要求：找出数列中指定index位置的数值

实现：

[html] view plaincopy

span style="font-size:12px;"  // 利用递归实现了Fibonacci数列      private static int fab(int index) {          if (index == 1 || index == 2) {              return 1;          } else {              return fab(index - 1) + fab(index - 2);          }      }/span

（3）汉诺塔

要求：汉诺塔挪动

实现：

[html] view plaincopy

span style="font-size:12px;"  span style="white-space:pre;" /spanprivate static final String DISK_B = "diskB";    span style="white-space:pre;"   /spanprivate static final String DISK_C = "diskC";    span style="white-space:pre;"   /spanprivate static final String DISK_A = "diskA";    span style="white-space:pre;"   /spanstatic String from=DISK_A;  span style="white-space:pre;" /span  static String to=DISK_C;  span style="white-space:pre;" /span  static String mid=DISK_B;    span style="white-space:pre;" /span  public static void main(String[] args) {  span style="white-space:pre;" /span      String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");  span style="white-space:pre;" /span      int num=Integer.parseInt(input);  span style="white-space:pre;" /span      move(num,from,mid,to);  span style="white-space:pre;" /span  }/span

[html] view plaincopy

span style="font-size:12px;"  // 利用递归实现汉诺塔      private static void move(int num, String from2, String mid2, String to2) {          if (num == 1) {              System.out.println("move disk 1 from " + from2 + " to " + to2);          } else {              move(num - 1, from2, to2, mid2);              System.out.println("move disk " + num + " from " + from2 + " to " + to2);              move(num - 1, mid2, from2, to2);          }      }/span

（4）排列组合

要求：将输入的一个字符串中的所有元素进行排序并输出，例如：你给出的参数是"abc"，

则程序会输出

abc

acb

bac

bca

cab

cba

实现：

[html] view plaincopy

span style="font-size:12px;"span style="white-space:pre;"   /spanpublic static void permute(String str) {   span style="white-space:pre;"    /span   char[] strArray = str.toCharArray();    span style="white-space:pre;"   /span permute(strArray, 0, strArray.length - 1);  span style="white-space:pre;" /span}/span

[html] view plaincopy

span style="font-size:12px;"  // 利用递归实现，将输入的一个字符串中的所有元素进行排序并输出      public static void permute(char[] list, int low, int high) {          int i;          if (low == high) {              String cout = "";              for (i = 0; i = high; i++) {                  cout += list[i];              }              System.out.println(cout);          } else {              for (i = low; i = high; i++) {                  char temp = list[low];                  list[low] = list[i];                  list[i] = temp;                  permute(list, low + 1, high);                  temp = list[low];