java的递归算法实现

A. java中，怎么打印出一个字符串的所有排列

在Java中，生成一个字符串的所有可能排列可以通过递归算法轻松实现。核心步骤是将字符串分为两部分：首字符和剩余字符，然后对首字符与剩余部分中的每个字符进行依次交换，并对剩余部分进行递归操作。这样，每次递归都会生成一个新的排列组合。下面是通过Java代码展示的实现过程：

首先，创建一个名为printPermutations的函数，它接收一个字符数组作为输入。函数从索引index开始，通过递归实现排列生成。在每次迭代中，它会交换arr[index]与arr[index+1]，然后递归处理arr从index+2到末尾的子数组。

当index等于字符串长度减一，意味着完成了一个完整的排列，这时将当前arr转换为字符串并输出。为了确保每次递归后能回溯到原始顺序，我们需要在交换后将字符恢复原位，再进行下一轮递归。

尽管这种方法直观且易于理解，但它的时间复杂度较高，存在重复计算。对于较长的字符串，可能需要考虑更为高效的排列算法，如使用动态规划等技术，以减少重复计算，提高效率。但对短字符串而言，递归方法已经足够满足需求。

B. 用递归算法求1~100的和，用java写。

递归是一种计算机科学的重要概念，它在程序设计中起到了关键作用。通过递归方法编写程序，可以使代码更加简洁、清晰。

在递归过程中，每次调用函数时，问题的规模都会有所缩小，通常情况下是减半或减小一定的量。

相邻两次递归调用之间存在紧密联系，前一次调用的结果将作为后一次调用的输入。这种依赖关系使得递归成为解决某些问题的强大工具。

当问题的规模足够小时，可以直接给出解答而不再进行递归调用。因此，每次递归调用都必须有条件限制，通常以规模未达到直接解答的大小为条件。若无条件递归调用，则可能会陷入死循环，无法正常结束。

以求1至100的和为例，可以使用递归算法实现。下面是一个Java示例：

public class Test {
public static void main(String[] args) {
System.out.println(dg(100));
}
static int dg(int i) {
int sum;
if (i == 1) {
return 1;
} else {
sum = i + dg(i - 1);
return sum;
}
}
}

在这个例子中，`dg`函数用于计算从1到给定整数`i`的所有整数之和。当`i`等于1时，直接返回1，否则将当前值`i`与`i-1`的和相加，并递归调用`dg(i-1)`。

递归算法的优势在于简化了代码逻辑，使得问题的解决过程更加直观。然而，需要注意的是，递归调用的深度不宜过大，否则可能会导致栈溢出。因此，在实际应用中，应当权衡递归与迭代算法的优劣，选择最适合解决问题的方法。

C. 用java递归方法实现

publicintfun(intn){
if(n==0||n==1)return1;
returnn*fun(n-1);
}

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

publicclass二分法递归查找{
	publicstaticvoidmain(String[]args){

		//定义数组,注意,二分查找数组必须是有序的数组!
		int[]arr={1,3,5,7,9,11,13,15,17};
		
		//接受查找后的返回值:索引值,如果没有则是-1;
		//测试查找元素:9
		inta=binary(arr,9,0,arr.length-1);
		System.out.println("被查找数字索引位置在:"+a);
	}
	//参数列表依次为:被查找的数组,查找的数字,头索引,尾索引!
	publicstaticintbinary(int[]arr,intkey,intstar,intend)//递归
	{
		//每次进来创建,中间索引值!
		intmid=(star+end)/2;
		//如果被查找数小于头,或者尾,或者头索引大于尾索引,则说明无该数,返回-1;
		if(key<arr[star]||key>arr[end]||star>end){
			return-1;
		}
		//如果中间值小于被查找数,则重新定义头索引移至中间+1位置,筛选掉一半数字!
		if(arr[mid]<key){
			//开始递归!
			returnbinary(arr,key,mid+1,end);
			//否则如果中间值大于被查找数,则重新尾索引移至中间-1位置,筛选掉一半数字!
		}elseif(arr[mid]>key){
			//开始递归!
			returnbinary(arr,key,star,mid-1);
		}else{
			//否者就是找到了,返回该索引!
			returnmid;
		}
	}
}

E. 用java冒泡排序和递归算法

冒泡排序

（1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

（2）用java实现

ublicclassbubbleSort{

publicbubbleSort(){

inta[]={1,54,6,3,78,34,12,45};

inttemp=0;

for(inti=0;i<a.length;i++){

for(intj=i+1;j<a.length;j++){

if(a[i]>a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

for(inti=0;i<a.length;i++)

System.out.println(a[i]);

}

}

递归

递归算法，就是程序的自身调用。表现在一段程序中往往会遇到调用自身的那样一种coding策略，可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。

java代码：

packagecom.cjq.filedown;

publicclassFab{

publicstaticvoidmain(Stringargs[]){
System.out.println(fab(5));
}

privatestaticintfab(intindex){
if(index==1||index==2){
return1;
}else{
returnfab(index-1)+fab(index-2);
}
}
}

F. java递归算法的例子。

阶乘：

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

实现：

[html] view plain

<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 plain

<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 plain

<span style="font-size:12px;"> <span style="white-space:pre;"> </span>private static final String DISK_B = "diskB"; <span style="white-space:pre;"> </span>private static final String DISK_C = "diskC"; <span style="white-space:pre;"> </span>private static final String DISK_A = "diskA"; <span style="white-space:pre;"> </span>static 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 plain

<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 plain

<span style="font-size:12px;"><span style="white-space:pre;"> </span>public 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 plain

<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];