帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之遞歸
1、遞歸的定義
遞歸，就是在運行的過程中調(diào)用自己。
遞歸必須要有三個要素：
- ①、邊界條件
- ②、遞歸前進(jìn)段
- ③、遞歸返回段
當(dāng)邊界條件不滿足時，遞歸前進(jìn)；當(dāng)邊界條件滿足時，遞歸返回。
2、求一個數(shù)的階乘：n!
規(guī)定：
①、0！=1
②、1！=1
③、負(fù)數(shù)沒有階乘
上面的表達(dá)式我們先用for循環(huán)改寫：
/**
* 0！=1 1！=1
* 負(fù)數(shù)沒有階乘,如果輸入負(fù)數(shù)返回-1
* @param n
* @return
*/
public static int getFactorialFor(int n){
int temp = 1;
if(n >=0){
for(int i = 1 ; i <= n ; i++){
temp = temp*i;
}
}else{
return -1;
}
return temp;
}如果求階乘的表達(dá)式是這樣的呢？
n! = n*(n-1)！
我們用遞歸來改寫：
/**
* 0！=1 1！=1
* 負(fù)數(shù)沒有階乘,如果輸入負(fù)數(shù)返回-1
* @param n
* @return
*/
public static int getFactorial(int n){
if(n >= 0){
if(n==0){
System.out.println(n+"!=1");
return 1;
}else{
System.out.println(n);
int temp = n*getFactorial(n-1);
System.out.println(n+"!="+temp);
return temp;
}
}
return -1;
}我們調(diào)用該方法getFactorial(4);即求4！打印如下：
這段遞歸程序的邊界條件就是n==0時，返回1，具體調(diào)用過程如下：
3、遞歸的二分查找
注意：二分查找的數(shù)組一定是有序的?。。?/p>
在有序數(shù)組array[]中，不斷將數(shù)組的中間值（mid）和被查找的值比較，如果被查找的值等于array[mid],就返回下標(biāo)mid; 否則，就將查找范圍縮小一半。如果被查找的值小于array[mid], 就繼續(xù)在左半邊查找;如果被查找的值大于array[mid], 就繼續(xù)在右半邊查找。 直到查找到該值或者查找范圍為空時， 查找結(jié)束?！ ?/p>
不用遞歸的二分查找如下：
/**
* 找到目標(biāo)值返回數(shù)組下標(biāo)，找不到返回-1
* @param array
* @param key
* @return
*/
public static int findTwoPoint(int[] array,int key){
int start = 0;
int last = array.length-1;
while(start <= last){
int mid = (last-start)/2+start;//防止直接相加造成int范圍溢出
if(key == array[mid]){//查找值等于當(dāng)前值，返回數(shù)組下標(biāo)
return mid;
}
if(key > array[mid]){//查找值比當(dāng)前值大
start = mid+1;
}
if(key < array[mid]){//查找值比當(dāng)前值小
last = mid-1;
}
}
return -1;
}二分查找用遞歸來改寫，相信也很簡單。邊界條件是找到當(dāng)前值，或者查找范圍為空。否則每一次查找都將范圍縮小一半。
public static int search(int[] array,int key,int low,int high){
int mid = (high-low)/2+low;
if(key == array[mid]){//查找值等于當(dāng)前值，返回數(shù)組下標(biāo)
return mid;
}else if(low > high){//找不到查找值，返回-1
return -1;
}else{
if(key < array[mid]){//查找值比當(dāng)前值小
return search(array,key,low,mid-1);
}
if(key > array[mid]){//查找值比當(dāng)前值大
return search(array,key,mid+1,high);
}
}
return -1;
}遞歸的二分查找和非遞歸的二分查找效率都為O(logN)，遞歸的二分查找更加簡潔，便于理解，但是速度會比非遞歸的慢。
4、分治算法
當(dāng)我們求解某些問題時，由于這些問題要處理的數(shù)據(jù)相當(dāng)多，或求解過程相當(dāng)復(fù)雜，使得直接求解法在時間上相當(dāng)長，或者根本無法直接求出。對于這類問題，我們往往先把它分解成幾個子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個問題的解法。如果這些子問題還較大，難以解決，可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。
上面講的遞歸的二分查找法就是一個分治算法的典型例子，分治算法常常是一個方法，在這個方法中含有兩個對自身的遞歸調(diào)用，分別對應(yīng)于問題的兩個部分。
二分查找中，將查找范圍分成比查找值大的一部分和比查找值小的一部分，每次遞歸調(diào)用只會有一個部分執(zhí)行。
5、漢諾塔問題
漢諾塔問題是由很多放置在三個塔座上的盤子組成的一個古老的難題。如下圖所示，所有盤子的直徑是不同的，并且盤子中央都有一個洞使得它們剛好可以放在塔座上。所有的盤子剛開始都放置在A 塔座上。這個難題的目標(biāo)是將所有的盤子都從塔座A移動到塔座C上，每次只可以移動一個盤子，并且任何一個盤子都不可以放置在比自己小的盤子之上。
試想一下，如果只有兩個盤子，盤子從小到大我們以數(shù)字命名（也可以想象為直徑），兩個盤子上面就是盤子1，下面是盤子2，那么我們只需要將盤子1先移動到B塔座上，然后將盤子2移動到C塔座，最后將盤子1移動到C塔座上。即完成2個盤子從A到C的移動。
如果有三個盤子，那么我們將盤子1放到C塔座，盤子2放到B塔座，在將C塔座的盤子1放到B塔座上，然后將A塔座的盤子3放到C塔座上，然后將B塔座的盤子1放到A塔座，將B塔座的盤子2放到C塔座，最后將A塔座的盤子1放到C塔座上。
如果有四個，五個，N個盤子，那么我們應(yīng)該怎么去做？這時候遞歸的思想就很好解決這樣的問題了，當(dāng)只有兩個盤子的時候，我們只需要將B塔座作為中介，將盤子1先放到中介塔座B上，然后將盤子2放到目標(biāo)塔座C上，最后將中介塔座B上的盤子放到目標(biāo)塔座C上即可。
所以無論有多少個盤子，我們都將其看做只有兩個盤子。假設(shè)有 N 個盤子在塔座A上，我們將其看為兩個盤子，其中(N-1)~1個盤子看成是一個盤子，最下面第N個盤子看成是一個盤子，那么解決辦法為：
- ①、先將A塔座的第(N-1)~1個盤子看成是一個盤子，放到中介塔座B上，然后將第N個盤子放到目標(biāo)塔座C上。
- ②、然后A塔座為空，看成是中介塔座，B塔座這時候有N-1個盤子，將第(N-2)~1個盤子看成是一個盤子，放到中介塔座A上，然后將B塔座的第(N-1)號盤子放到目標(biāo)塔座C上。
- ③、這時候A塔座上有(N-2)個盤子，B塔座為空，又將B塔座視為中介塔座，重復(fù)①，②步驟，直到所有盤子都放到目標(biāo)塔座C上結(jié)束。
簡單來說，跟把大象放進(jìn)冰箱的步驟一樣，遞歸算法為：
- ①、從初始塔座A上移動包含n-1個盤子到中介塔座B上。
- ②、將初始塔座A上剩余的一個盤子（最大的一個盤子）放到目標(biāo)塔座C上。
- ③、將中介塔座B上n-1個盤子移動到目標(biāo)塔座C上。
/**
* 漢諾塔問題
* @param dish 盤子個數(shù)(也表示名稱)
* @param from 初始塔座
* @param temp 中介塔座
* @param to 目標(biāo)塔座
*/
public static void move(int dish,String from,String temp,String to){
if(dish == 1){
System.out.println("將盤子"+dish+"從塔座"+from+"移動到目標(biāo)塔座"+to);
}else{
move(dish-1,from,to,temp);//A為初始塔座，B為目標(biāo)塔座，C為中介塔座
System.out.println("將盤子"+dish+"從塔座"+from+"移動到目標(biāo)塔座"+to);
move(dish-1,temp,from,to);//B為初始塔座，C為目標(biāo)塔座，A為中介塔座
}
}測試：
move(3,"A","B","C");
打印結(jié)果為：
6、歸并排序
歸并算法的中心是歸并兩個已經(jīng)有序的數(shù)組。歸并兩個有序數(shù)組A和B，就生成了第三個有序數(shù)組C。數(shù)組C包含數(shù)組A和B的所有數(shù)據(jù)項。
非遞歸算法為：
/**
* 傳入兩個有序數(shù)組a和b，返回一個排好序的合并數(shù)組
* @param a
* @param b
* @return
*/
public static int[] sort(int[] a,int[] b){
int[] c = new int[a.length+b.length];
int aNum = 0,bNum = 0,cNum=0;
while(aNum<a.length && bNum < b.length){
if(a[aNum] >= b[bNum]){//比較a數(shù)組和b數(shù)組的元素，誰更小將誰賦值到c數(shù)組
c[cNum++] = b[bNum++];
}else{
c[cNum++] = a[aNum++];
}
}
//如果a數(shù)組全部賦值到c數(shù)組了，但是b數(shù)組還有元素，則將b數(shù)組剩余元素按順序全部復(fù)制到c數(shù)組
while(aNum == a.length && bNum < b.length){
c[cNum++] = b[bNum++];
}
//如果b數(shù)組全部賦值到c數(shù)組了，但是a數(shù)組還有元素，則將a數(shù)組剩余元素按順序全部復(fù)制到c數(shù)組
while(bNum == b.length && aNum < a.length){
c[cNum++] = a[aNum++];
}
return c;
}該方法有三個while循環(huán)，第一個while比較數(shù)組a和數(shù)組b的元素，并將較小的賦值到數(shù)組c；第二個while循環(huán)當(dāng)a數(shù)組所有元素都已經(jīng)賦值到c數(shù)組之后，而b數(shù)組還有元素，那么直接把b數(shù)組剩余的元素賦值到c數(shù)組；第三個while循環(huán)則是b數(shù)組所有元素都已經(jīng)賦值到c數(shù)組了，而a數(shù)組還有剩余元素，那么直接把a數(shù)組剩余的元素全部賦值到c數(shù)組。
歸并排序的思想是把一個數(shù)組分成兩半，排序每一半，然后用上面的sort()方法將數(shù)組的兩半歸并成為一個有序的數(shù)組。如何來為每一部分排序呢？這里我們利用遞歸的思想：
把每一半都分為四分之一，對每個四分之一進(jìn)行排序，然后把它們歸并成一個有序的一半。類似的，如何給每個四分之一數(shù)組排序呢？把每個四分之一分成八分之一，對每個八分之一進(jìn)行排序，以此類推，反復(fù)的分割數(shù)組，直到得到的子數(shù)組是一個數(shù)據(jù)項，那這就是這個遞歸算法的邊界值，也就是假定一個數(shù)據(jù)項的元素是有序的?！ ?/p>
public static int[] mergeSort(int[] c,int start,int last){
if(last > start){
//也可以是(start+last)/2，這樣寫是為了防止數(shù)組長度很大造成兩者相加超過int范圍，導(dǎo)致溢出
int mid = start + (last - start)/2;
mergeSort(c,start,mid);//左邊數(shù)組排序
mergeSort(c,mid+1,last);//右邊數(shù)組排序
merge(c,start,mid,last);//合并左右數(shù)組
}
return c;
}
public static void merge(int[] c,int start,int mid,int last){
int[] temp = new int[last-start+1];//定義臨時數(shù)組
int i = start;//定義左邊數(shù)組的下標(biāo)
int j = mid + 1;//定義右邊數(shù)組的下標(biāo)
int k = 0;
while(i <= mid && j <= last){
if(c[i] < c[j]){
temp[k++] = c[i++];
}else{
temp[k++] = c[j++];
}
}
//把左邊剩余數(shù)組元素移入新數(shù)組中
while(i <= mid){
temp[k++] = c[i++];
}
//把右邊剩余數(shù)組元素移入到新數(shù)組中
while(j <= last){
temp[k++] = c[j++];
}
//把新數(shù)組中的數(shù)覆蓋到c數(shù)組中
for(int k2 = 0 ; k2 < temp.length ; k2++){
c[k2+start] = temp[k2];
}
}測試：
int[] c = {2,7,8,3,1,6,9,0,5,4};
c = mergeSort(c,0,c.length-1);
System.out.println(Arrays.toString(c));結(jié)果為：
7、消除遞歸
一個算法作為一個遞歸的方法通常通概念上很容易理解，但是遞歸的使用在方法的調(diào)用和返回都會有額外的開銷，通常情況下，用遞歸能實現(xiàn)的，用循環(huán)都可以實現(xiàn)，而且循環(huán)的效率會更高，所以在實際應(yīng)用中，把遞歸的算法轉(zhuǎn)換為非遞歸的算法是非常有用的。這種轉(zhuǎn)換通常會使用到棧。
遞歸和棧
遞歸和棧有這緊密的聯(lián)系，而且大多數(shù)編譯器都是用棧來實現(xiàn)遞歸的，當(dāng)調(diào)用一個方法時，編譯器會把這個方法的所有參數(shù)和返回地址都壓入棧中，然后把控制轉(zhuǎn)移給這個方法。當(dāng)這個方法返回時，這些值退棧。參數(shù)消失了，并且控制權(quán)重新回到返回地址處。
調(diào)用一個方法時所發(fā)生的事：
一、當(dāng)一個方法被調(diào)用時，它的參數(shù)和返回地址被壓入一個棧中；
二、這個方法可以通過獲取棧頂元素的值來訪問它的參數(shù)；
三、當(dāng)這個方法要返回時，它查看棧以獲得返回地址，然后這個地址以及方法的所有參數(shù)退棧，并且銷毀。
8、遞歸的有趣應(yīng)用
①、求一個數(shù)的乘方
一般稍微復(fù)雜一點的計算器上面都能求一個數(shù)的乘法，通常計算器上面的標(biāo)志是 x^y 這樣的按鍵，表示求 x 的 y 次方。一般情況下我們是如何求一個數(shù)的乘法的呢？
比如2^8,我們可以會求表達(dá)式2*2*2*2*2*2*2*2 的值，但是如果y的值很大，這個會顯得表達(dá)式很冗長。那么由沒有更快一點方法呢？
數(shù)學(xué)公式如下是成立的：
(Xa)b = Xa*b
如果如果求28次方，我們可以先假定22=a,于是28 = （22）4，那么就是a4；假定 a2 = b，那么 a4 = b2，而b2可以寫成(b2)1。于是現(xiàn)在28就轉(zhuǎn)換成：b*b
也就是說我們將乘方的運算轉(zhuǎn)換為乘法的運算。
求xy的值，當(dāng)y是偶數(shù)的時候，最后能轉(zhuǎn)換成兩個數(shù)相乘，當(dāng)時當(dāng)y是奇數(shù)的時候，最后我們必須要在返回值后面額外的乘以一個x。
x^y= (x^2)^(y/2)，定義a=x^2,b=y/2, 則得到形如： x^y= a^b;
具體算法：
public static int pow(int x,int y){
if(x == 0 || x == 1){
return x;
}
if(y > 1){
int b = y/2;
int a = x*x;
if(y%2 == 1){//y為奇數(shù)
return pow(a,b)*x;
}else{//y為偶數(shù)
return pow(a,b);
}
}else if(y == 0){
return 1;
}else{//y==1
return x;
}
}②、背包問題
背包問題也是計算機中的經(jīng)典問題。在最簡單的形式中，包括試圖將不同重量的數(shù)據(jù)項放到背包中，以使得背包最后達(dá)到指定的總重量。
比如：假設(shè)想要讓背包精確地承重20磅，并且有 5 個可以放入的數(shù)據(jù)項，它們的重量分別是 11 磅，8 磅，7 磅，6 磅，5 磅。這個問題可能對于人類來說很簡單，我們大概就可以計算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果讓計算機來解決這個問題，就需要給計算機設(shè)定詳細(xì)的指令了。
算法如下：
一、如果在這個過程的任何時刻，選擇的數(shù)據(jù)項的總和符合目標(biāo)重量，那么工作便完成了。
二、從選擇的第一個數(shù)據(jù)項開始，剩余的數(shù)據(jù)項的加和必須符合背包的目標(biāo)重量減去第一個數(shù)據(jù)項的重量，這是一個新的目標(biāo)重量。
三、逐個的試每種剩余數(shù)據(jù)項組合的可能性，但是注意不要去試所有的組合，因為只要數(shù)據(jù)項的和大于目標(biāo)重量的時候，就停止添加數(shù)據(jù)。
四、如果沒有合適的組合，放棄第一個數(shù)據(jù)項，并且從第二個數(shù)據(jù)項開始再重復(fù)一遍整個過程。
五、繼續(xù)從第三個數(shù)據(jù)項開始，如此下去直到你已經(jīng)試驗了所有的組合，這時才知道有沒有解決方案。
具體實現(xiàn)過程：
package com.ys.recursion;
public class Knapsack {
private int[] weights; //可供選擇的重量
private boolean[] selects; //記錄是否被選擇
public Knapsack(int[] weights){
this.weights = weights;
selects = new boolean[weights.length];
}
/**
* 找出符合承重重量的組合
* @param total 總重量
* @param index 可供選擇的重量下標(biāo)
*/
public void knapsack(int total,int index){
if(total < 0 || total > 0 && index >= weights.length){
return;//沒找到解決辦法，直接返回
}
if(total == 0){//總重量為0，則找到解決辦法了
for(int i = 0 ; i < index ; i++){
if(selects[i] == true){
System.out.println(weights[i]+" ");
}
}
System.out.println();
return;
}
selects[index] = true;
knapsack(total-weights[index], index+1);
selects[index] = false;
knapsack(total, index+1);
}
public static void main(String[] args) {
int array[] = {11,9,7,6,5};
int total = 20;
Knapsack k = new Knapsack(array);
k.knapsack(total, 0);
}
}③、組合：選擇一支隊伍
在數(shù)學(xué)中，組合是對事物的一種選擇，而不考慮他們的順序。
比如有5個登山隊員，名稱為 A,B,C,D和E。想要從這五個隊員中選擇三個隊員去登峰，這時候如何列出所有的隊員組合。（不考慮順序）
還是以遞歸的思想來解決：首先這五個人的組合選擇三個人分成兩個部分，第一部分包含A隊員，第二部分不包含A隊員。假設(shè)把從 5 個人中選出 3 個人的組合簡寫為（5,3），規(guī)定 n 是這群人的大小，并且 k 是組隊的大小。那么根據(jù)法則可以有：
(n,k) = (n-1,k-1) + (n-1,k)
對于從 5 個人中選擇 3 個人，有：
(5,3) = (4,2)+(4,3)
(4,2)表示已經(jīng)有A隊員了，然后從剩下的4個隊員中選擇2個隊員，(4,3)表示從5個人中剔除A隊員，從剩下的4個隊員中選擇3個隊員，這兩種情況相加就是從5個隊員中選擇3個隊員。
現(xiàn)在已經(jīng)把一個大問題轉(zhuǎn)換為兩個小問題了。從4個人的人群中做兩次選擇（一次選擇2個，一次選擇3個），而不是從5個人的人群中選擇3個。
從4個人的人群中選擇2個人，又可以表示為：(4,2) = (3,1) + (3,2)，以此類推，很容易想到遞歸的思想。
具體實現(xiàn)代碼：
package com.ys.recursion;
public class Combination {
private char[] persons;//組中所有可供選擇的人員
private boolean[] selects;//標(biāo)記成員是否被選中，選中為true
public Combination(char[] persons){
this.persons = persons;
selects = new boolean[persons.length];
}
public void showTeams(int teamNumber){
combination(teamNumber,0);
}
/**
*
* @param teamNumber 需要選擇的隊員數(shù)
* @param index 從第幾個隊員開始選擇
*/
public void combination(int teamNumber,int index){
if(teamNumber == 0){//當(dāng)teamNumber=0時，找到一組
for(int i = 0 ; i < selects.length ; i++){
if(selects[i] == true){
System.out.print(persons[i]+" ");
}
}
System.out.println();
return;
}
//index超過組中人員總數(shù)，表示未找到
if(index >= persons.length ){
return;
}
selects[index] = true;
combination(teamNumber-1, index+1);
selects[index] = false;
combination(teamNumber, index+1);
}
public static void main(String[] args) {
char[] persons = {'A','B','C','D','E'};
Combination cb = new Combination(persons);
cb.showTeams(3);
}
}
9、總結(jié)
一個遞歸方法每次都是用不同的參數(shù)值反復(fù)調(diào)用自己，當(dāng)某種參數(shù)值使得遞歸的方法返回，而不再調(diào)用自身，這種情況稱為邊界值，也叫基值。當(dāng)遞歸方法返回時，遞歸過程通過逐漸完成各層方法實例的未執(zhí)行部分，而從最內(nèi)層返回到最外層的原始調(diào)用處。
階乘、漢諾塔、歸并排序等都可以用遞歸來實現(xiàn)，但是要注意任何可以用遞歸完成的算法用棧都能實現(xiàn)。當(dāng)我們發(fā)現(xiàn)遞歸的方法效率比較低時，可以考慮用循環(huán)或者棧來代替它。
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要介紹了Spring依賴注入的兩種方式（根據(jù)實例詳解）,非常具有實用價值，需要的朋友可以參考下2017-05-05
這篇文章主要介紹了IDEA安裝阿里代碼規(guī)范插件的步驟，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-12-12
SpringBoot整合TomCat實現(xiàn)本地圖片服務(wù)器代碼解析
這篇文章主要介紹了SpringBoot整合TomCat實現(xiàn)本地圖片服務(wù)器代碼解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
這篇文章介紹了JAVA垃圾收集器與內(nèi)存分配策略，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2015-07-07
SpringBoot開發(fā)技巧之如何處理跨域請求CORS
CORS（Cross-Origin Resource Sharing）"跨域資源共享"，是一個W3C標(biāo)準(zhǔn)，它允許瀏覽器向跨域服務(wù)器發(fā)送Ajax請求，打破了Ajax只能訪問本站內(nèi)的資源限制2021-10-10
這篇文章主要介紹了解決kafka消息堆積及分區(qū)不均勻的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
本文提供了找出鏈表倒數(shù)第n個節(jié)點元素的二個方法，其中一個方法是JAVA代碼實現(xiàn)2013-11-11
Java中ReentrantLock和ReentrantReadWriteLock的原理
這篇文章主要介紹了Java中ReentrantLock和ReentrantReadWriteLock的原理，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，感興趣的小伙伴可以參考一下2022-09-09
SpringCloud-Alibaba-Sentinel-配置持久化策略詳解
這篇文章主要介紹了SpringCloud-Alibaba-Sentinel-配置持久化策略,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
Sping?Security前后端分離兩種實戰(zhàn)方案
這篇文章主要介紹了Sping?Security前后端分離兩種方案,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03