1、遞歸的定義

遞歸，就是在運(yùn)行的過(guò)程中調(diào)用自己。

遞歸必須要有三個(gè)要素：

• ①、邊界條件
• ②、遞歸前進(jìn)段
• ③、遞歸返回段

當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。

2、求一個(gè)數(shù)的階乘：n!

規(guī)定：

①、0！=1

②、1！=1

③、負(fù)數(shù)沒(méi)有階乘

上面的表達(dá)式我們先用for循環(huán)改寫(xiě)：

/**
 * 0！=1  1！=1
 * 負(fù)數(shù)沒(méi)有階乘,如果輸入負(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)！

我們用遞歸來(lái)改寫(xiě)：

/**
 * 0！=1  1！=1
 * 負(fù)數(shù)沒(méi)有階乘,如果輸入負(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時(shí)，返回1，具體調(diào)用過(guò)程如下：

3、遞歸的二分查找

注意：二分查找的數(shù)組一定是有序的?。?！

在有序數(shù)組array[]中，不斷將數(shù)組的中間值（mid）和被查找的值比較，如果被查找的值等于array[mid],就返回下標(biāo)mid; 否則，就將查找范圍縮小一半。如果被查找的值小于array[mid], 就繼續(xù)在左半邊查找;如果被查找的值大于array[mid], 就繼續(xù)在右半邊查找。 直到查找到該值或者查找范圍為空時(shí)， 查找結(jié)束?！　?/p>

不用遞歸的二分查找如下：

/**
 * 找到目標(biāo)值返回?cái)?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)前值，返回?cái)?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;
}

二分查找用遞歸來(lái)改寫(xiě)，相信也很簡(jiǎn)單。邊界條件是找到當(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)前值，返回?cái)?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)，遞歸的二分查找更加簡(jiǎn)潔，便于理解，但是速度會(huì)比非遞歸的慢。

4、分治算法

當(dāng)我們求解某些問(wèn)題時(shí)，由于這些問(wèn)題要處理的數(shù)據(jù)相當(dāng)多，或求解過(guò)程相當(dāng)復(fù)雜，使得直接求解法在時(shí)間上相當(dāng)長(zhǎng)，或者根本無(wú)法直接求出。對(duì)于這類問(wèn)題，我們往往先把它分解成幾個(gè)子問(wèn)題，找到求出這幾個(gè)子問(wèn)題的解法后，再找到合適的方法，把它們組合成求整個(gè)問(wèn)題的解法。如果這些子問(wèn)題還較大，難以解決，可以再把它們分成幾個(gè)更小的子問(wèn)題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。

上面講的遞歸的二分查找法就是一個(gè)分治算法的典型例子，分治算法常常是一個(gè)方法，在這個(gè)方法中含有兩個(gè)對(duì)自身的遞歸調(diào)用，分別對(duì)應(yīng)于問(wèn)題的兩個(gè)部分。

二分查找中，將查找范圍分成比查找值大的一部分和比查找值小的一部分，每次遞歸調(diào)用只會(huì)有一個(gè)部分執(zhí)行。

5、漢諾塔問(wèn)題

漢諾塔問(wèn)題是由很多放置在三個(gè)塔座上的盤(pán)子組成的一個(gè)古老的難題。如下圖所示，所有盤(pán)子的直徑是不同的，并且盤(pán)子中央都有一個(gè)洞使得它們剛好可以放在塔座上。所有的盤(pán)子剛開(kāi)始都放置在A 塔座上。這個(gè)難題的目標(biāo)是將所有的盤(pán)子都從塔座A移動(dòng)到塔座C上，每次只可以移動(dòng)一個(gè)盤(pán)子，并且任何一個(gè)盤(pán)子都不可以放置在比自己小的盤(pán)子之上?！　?/p>

試想一下，如果只有兩個(gè)盤(pán)子，盤(pán)子從小到大我們以數(shù)字命名（也可以想象為直徑），兩個(gè)盤(pán)子上面就是盤(pán)子1，下面是盤(pán)子2，那么我們只需要將盤(pán)子1先移動(dòng)到B塔座上，然后將盤(pán)子2移動(dòng)到C塔座，最后將盤(pán)子1移動(dòng)到C塔座上。即完成2個(gè)盤(pán)子從A到C的移動(dòng)。

如果有三個(gè)盤(pán)子，那么我們將盤(pán)子1放到C塔座，盤(pán)子2放到B塔座，在將C塔座的盤(pán)子1放到B塔座上，然后將A塔座的盤(pán)子3放到C塔座上，然后將B塔座的盤(pán)子1放到A塔座，將B塔座的盤(pán)子2放到C塔座，最后將A塔座的盤(pán)子1放到C塔座上。

如果有四個(gè)，五個(gè)，N個(gè)盤(pán)子，那么我們應(yīng)該怎么去做？這時(shí)候遞歸的思想就很好解決這樣的問(wèn)題了，當(dāng)只有兩個(gè)盤(pán)子的時(shí)候，我們只需要將B塔座作為中介，將盤(pán)子1先放到中介塔座B上，然后將盤(pán)子2放到目標(biāo)塔座C上，最后將中介塔座B上的盤(pán)子放到目標(biāo)塔座C上即可。

所以無(wú)論有多少個(gè)盤(pán)子，我們都將其看做只有兩個(gè)盤(pán)子。假設(shè)有 N 個(gè)盤(pán)子在塔座A上，我們將其看為兩個(gè)盤(pán)子，其中(N-1)~1個(gè)盤(pán)子看成是一個(gè)盤(pán)子，最下面第N個(gè)盤(pán)子看成是一個(gè)盤(pán)子，那么解決辦法為：

• ①、先將A塔座的第(N-1)~1個(gè)盤(pán)子看成是一個(gè)盤(pán)子，放到中介塔座B上，然后將第N個(gè)盤(pán)子放到目標(biāo)塔座C上。
• ②、然后A塔座為空，看成是中介塔座，B塔座這時(shí)候有N-1個(gè)盤(pán)子，將第(N-2)~1個(gè)盤(pán)子看成是一個(gè)盤(pán)子，放到中介塔座A上，然后將B塔座的第(N-1)號(hào)盤(pán)子放到目標(biāo)塔座C上。
• ③、這時(shí)候A塔座上有(N-2)個(gè)盤(pán)子，B塔座為空，又將B塔座視為中介塔座，重復(fù)①，②步驟，直到所有盤(pán)子都放到目標(biāo)塔座C上結(jié)束。

簡(jiǎn)單來(lái)說(shuō)，跟把大象放進(jìn)冰箱的步驟一樣，遞歸算法為：

• ①、從初始塔座A上移動(dòng)包含n-1個(gè)盤(pán)子到中介塔座B上。
• ②、將初始塔座A上剩余的一個(gè)盤(pán)子（最大的一個(gè)盤(pán)子）放到目標(biāo)塔座C上。
• ③、將中介塔座B上n-1個(gè)盤(pán)子移動(dòng)到目標(biāo)塔座C上。

/**
 * 漢諾塔問(wèn)題
 * @param dish 盤(pán)子個(gè)數(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("將盤(pán)子"+dish+"從塔座"+from+"移動(dòng)到目標(biāo)塔座"+to);
    }else{
        move(dish-1,from,to,temp);//A為初始塔座，B為目標(biāo)塔座，C為中介塔座
        System.out.println("將盤(pán)子"+dish+"從塔座"+from+"移動(dòng)到目標(biāo)塔座"+to);
        move(dish-1,temp,from,to);//B為初始塔座，C為目標(biāo)塔座，A為中介塔座
    }
}

測(cè)試：

move(3,"A","B","C");

打印結(jié)果為：

6、歸并排序

歸并算法的中心是歸并兩個(gè)已經(jīng)有序的數(shù)組。歸并兩個(gè)有序數(shù)組A和B，就生成了第三個(gè)有序數(shù)組C。數(shù)組C包含數(shù)組A和B的所有數(shù)據(jù)項(xiàng)。

非遞歸算法為：

/**
 * 傳入兩個(gè)有序數(shù)組a和b，返回一個(gè)排好序的合并數(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ù)組的元素，誰(shuí)更小將誰(shuí)賦值到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;
}

該方法有三個(gè)while循環(huán)，第一個(gè)while比較數(shù)組a和數(shù)組b的元素，并將較小的賦值到數(shù)組c；第二個(gè)while循環(huán)當(dāng)a數(shù)組所有元素都已經(jīng)賦值到c數(shù)組之后，而b數(shù)組還有元素，那么直接把b數(shù)組剩余的元素賦值到c數(shù)組；第三個(gè)while循環(huán)則是b數(shù)組所有元素都已經(jīng)賦值到c數(shù)組了，而a數(shù)組還有剩余元素，那么直接把a(bǔ)數(shù)組剩余的元素全部賦值到c數(shù)組。

歸并排序的思想是把一個(gè)數(shù)組分成兩半，排序每一半，然后用上面的sort()方法將數(shù)組的兩半歸并成為一個(gè)有序的數(shù)組。如何來(lái)為每一部分排序呢？這里我們利用遞歸的思想：

把每一半都分為四分之一，對(duì)每個(gè)四分之一進(jìn)行排序，然后把它們歸并成一個(gè)有序的一半。類似的，如何給每個(gè)四分之一數(shù)組排序呢？把每個(gè)四分之一分成八分之一，對(duì)每個(gè)八分之一進(jìn)行排序，以此類推，反復(fù)的分割數(shù)組，直到得到的子數(shù)組是一個(gè)數(shù)據(jù)項(xiàng)，那這就是這個(gè)遞歸算法的邊界值，也就是假定一個(gè)數(shù)據(jù)項(xiàng)的元素是有序的?！　?/p>

public static int[] mergeSort(int[] c,int start,int last){
    if(last > start){
        //也可以是(start+last)/2，這樣寫(xiě)是為了防止數(shù)組長(zhǎng)度很大造成兩者相加超過(guò)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í)數(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];
    }
}

測(cè)試：

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、消除遞歸

一個(gè)算法作為一個(gè)遞歸的方法通常通概念上很容易理解，但是遞歸的使用在方法的調(diào)用和返回都會(huì)有額外的開(kāi)銷，通常情況下，用遞歸能實(shí)現(xiàn)的，用循環(huán)都可以實(shí)現(xiàn)，而且循環(huán)的效率會(huì)更高，所以在實(shí)際應(yīng)用中，把遞歸的算法轉(zhuǎn)換為非遞歸的算法是非常有用的。這種轉(zhuǎn)換通常會(huì)使用到棧。

遞歸和棧

遞歸和棧有這緊密的聯(lián)系，而且大多數(shù)編譯器都是用棧來(lái)實(shí)現(xiàn)遞歸的，當(dāng)調(diào)用一個(gè)方法時(shí)，編譯器會(huì)把這個(gè)方法的所有參數(shù)和返回地址都?jí)喝霔Ｖ?，然后把控制轉(zhuǎn)移給這個(gè)方法。當(dāng)這個(gè)方法返回時(shí)，這些值退棧。參數(shù)消失了，并且控制權(quán)重新回到返回地址處。

調(diào)用一個(gè)方法時(shí)所發(fā)生的事：

一、當(dāng)一個(gè)方法被調(diào)用時(shí)，它的參數(shù)和返回地址被壓入一個(gè)棧中；

二、這個(gè)方法可以通過(guò)獲取棧頂元素的值來(lái)訪問(wèn)它的參數(shù)；

三、當(dāng)這個(gè)方法要返回時(shí)，它查看棧以獲得返回地址，然后這個(gè)地址以及方法的所有參數(shù)退棧，并且銷毀。

8、遞歸的有趣應(yīng)用　　

①、求一個(gè)數(shù)的乘方

一般稍微復(fù)雜一點(diǎn)的計(jì)算器上面都能求一個(gè)數(shù)的乘法，通常計(jì)算器上面的標(biāo)志是 x^y 這樣的按鍵，表示求 x 的 y 次方。一般情況下我們是如何求一個(gè)數(shù)的乘法的呢？

比如2^8,我們可以會(huì)求表達(dá)式2*2*2*2*2*2*2*2 的值，但是如果y的值很大，這個(gè)會(huì)顯得表達(dá)式很冗長(zhǎng)。那么由沒(méi)有更快一點(diǎn)方法呢？

數(shù)學(xué)公式如下是成立的：

(Xa)b = Xa*b

如果如果求28次方，我們可以先假定22=a,于是28 = （22）4，那么就是a4；假定 a2 = b，那么 a4 = b2，而b2可以寫(xiě)成(b2)1。于是現(xiàn)在28就轉(zhuǎn)換成：b*b

也就是說(shuō)我們將乘方的運(yùn)算轉(zhuǎn)換為乘法的運(yùn)算。

求xy的值，當(dāng)y是偶數(shù)的時(shí)候，最后能轉(zhuǎn)換成兩個(gè)數(shù)相乘，當(dāng)時(shí)當(dāng)y是奇數(shù)的時(shí)候，最后我們必須要在返回值后面額外的乘以一個(gè)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;
    }
}

②、背包問(wèn)題

背包問(wèn)題也是計(jì)算機(jī)中的經(jīng)典問(wèn)題。在最簡(jiǎn)單的形式中，包括試圖將不同重量的數(shù)據(jù)項(xiàng)放到背包中，以使得背包最后達(dá)到指定的總重量。

比如：假設(shè)想要讓背包精確地承重20磅，并且有 5 個(gè)可以放入的數(shù)據(jù)項(xiàng)，它們的重量分別是 11 磅，8 磅，7 磅，6 磅，5 磅。這個(gè)問(wèn)題可能對(duì)于人類來(lái)說(shuō)很簡(jiǎn)單，我們大概就可以計(jì)算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果讓計(jì)算機(jī)來(lái)解決這個(gè)問(wèn)題，就需要給計(jì)算機(jī)設(shè)定詳細(xì)的指令了。

算法如下：

一、如果在這個(gè)過(guò)程的任何時(shí)刻，選擇的數(shù)據(jù)項(xiàng)的總和符合目標(biāo)重量，那么工作便完成了。

二、從選擇的第一個(gè)數(shù)據(jù)項(xiàng)開(kāi)始，剩余的數(shù)據(jù)項(xiàng)的加和必須符合背包的目標(biāo)重量減去第一個(gè)數(shù)據(jù)項(xiàng)的重量，這是一個(gè)新的目標(biāo)重量。

三、逐個(gè)的試每種剩余數(shù)據(jù)項(xiàng)組合的可能性，但是注意不要去試所有的組合，因?yàn)橹灰獢?shù)據(jù)項(xiàng)的和大于目標(biāo)重量的時(shí)候，就停止添加數(shù)據(jù)。

四、如果沒(méi)有合適的組合，放棄第一個(gè)數(shù)據(jù)項(xiàng)，并且從第二個(gè)數(shù)據(jù)項(xiàng)開(kāi)始再重復(fù)一遍整個(gè)過(guò)程。

五、繼續(xù)從第三個(gè)數(shù)據(jù)項(xiàng)開(kāi)始，如此下去直到你已經(jīng)試驗(yàn)了所有的組合，這時(shí)才知道有沒(méi)有解決方案。

具體實(shí)現(xiàn)過(guò)程：

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;//沒(méi)找到解決辦法，直接返回
        }
        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);
    }
}

③、組合：選擇一支隊(duì)伍

在數(shù)學(xué)中，組合是對(duì)事物的一種選擇，而不考慮他們的順序。

比如有5個(gè)登山隊(duì)員，名稱為 A,B,C,D和E。想要從這五個(gè)隊(duì)員中選擇三個(gè)隊(duì)員去登峰，這時(shí)候如何列出所有的隊(duì)員組合。（不考慮順序）

還是以遞歸的思想來(lái)解決：首先這五個(gè)人的組合選擇三個(gè)人分成兩個(gè)部分，第一部分包含A隊(duì)員，第二部分不包含A隊(duì)員。假設(shè)把從 5 個(gè)人中選出 3 個(gè)人的組合簡(jiǎn)寫(xiě)為（5,3），規(guī)定 n 是這群人的大小，并且 k 是組隊(duì)的大小。那么根據(jù)法則可以有：

(n,k) = (n-1,k-1) + (n-1,k)

對(duì)于從 5 個(gè)人中選擇 3 個(gè)人，有：

　　(5,3) = (4,2)+(4,3)

(4,2)表示已經(jīng)有A隊(duì)員了，然后從剩下的4個(gè)隊(duì)員中選擇2個(gè)隊(duì)員，(4,3)表示從5個(gè)人中剔除A隊(duì)員，從剩下的4個(gè)隊(duì)員中選擇3個(gè)隊(duì)員，這兩種情況相加就是從5個(gè)隊(duì)員中選擇3個(gè)隊(duì)員。

現(xiàn)在已經(jīng)把一個(gè)大問(wèn)題轉(zhuǎn)換為兩個(gè)小問(wèn)題了。從4個(gè)人的人群中做兩次選擇（一次選擇2個(gè)，一次選擇3個(gè)），而不是從5個(gè)人的人群中選擇3個(gè)。

從4個(gè)人的人群中選擇2個(gè)人，又可以表示為：(4,2) = (3,1) + (3,2)，以此類推，很容易想到遞歸的思想。

具體實(shí)現(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 需要選擇的隊(duì)員數(shù)
     * @param index 從第幾個(gè)隊(duì)員開(kāi)始選擇
     */
    public void combination(int teamNumber,int index){
        if(teamNumber == 0){//當(dāng)teamNumber=0時(shí)，找到一組
            for(int i = 0 ; i < selects.length ; i++){
                if(selects[i] == true){
                    System.out.print(persons[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        //index超過(guò)組中人員總數(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é)

一個(gè)遞歸方法每次都是用不同的參數(shù)值反復(fù)調(diào)用自己，當(dāng)某種參數(shù)值使得遞歸的方法返回，而不再調(diào)用自身，這種情況稱為邊界值，也叫基值。當(dāng)遞歸方法返回時(shí)，遞歸過(guò)程通過(guò)逐漸完成各層方法實(shí)例的未執(zhí)行部分，而從最內(nèi)層返回到最外層的原始調(diào)用處。

階乘、漢諾塔、歸并排序等都可以用遞歸來(lái)實(shí)現(xiàn)，但是要注意任何可以用遞歸完成的算法用棧都能實(shí)現(xiàn)。當(dāng)我們發(fā)現(xiàn)遞歸的方法效率比較低時(shí)，可以考慮用循環(huán)或者棧來(lái)代替它。

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評(píng)論