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