什么是遞歸

百度百科：程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

借用知乎上Memoria的回答：

假設(shè)你在一個(gè)電影院，你想知道自己坐在哪一排，但是前面人很多，你懶得去數(shù)了，于是你問(wèn)前一排的人「你坐在哪一排？」，這樣前面的人 (代號(hào) A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了。不料 A 比你還懶，他也不想數(shù)，于是他也問(wèn)他前面的人 B「你坐在哪一排？」，這樣 A 可以用和你一模一樣的步驟知道自己所在的排。然后 B 也如法炮制。直到他們這一串人問(wèn)到了最前面的一排，第一排的人告訴問(wèn)問(wèn)題的人「我在第一排」。最后大家就都知道自己在哪一排了。

遞歸問(wèn)題分析的核心

一個(gè)合法的遞歸定義包含兩個(gè)部分：基礎(chǔ)情況和遞歸部分。

分析一個(gè)遞歸問(wèn)題就是列出遞歸定義表達(dá)式的過(guò)程。
上面那個(gè)電影院排數(shù)的問(wèn)題表達(dá)式可以列為：

f(n)={1,f(n?1)+1,n= 1n>1

幾個(gè)經(jīng)典題目

斐波那契數(shù)列

斐波那契數(shù)列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次類推下去，你會(huì)發(fā)現(xiàn)，它后一個(gè)數(shù)等于前面兩個(gè)數(shù)的和。在這個(gè)數(shù)列中的數(shù)字，就被稱為斐波那契數(shù)。

遞歸思想：一個(gè)數(shù)等于前兩個(gè)數(shù)的和。(這并不是廢話，這是執(zhí)行思路)

首先分析數(shù)列的遞歸表達(dá)式：

f(n)={n,f(n?1)+f(n?2),n<= 1n>1

代碼如下:

/*** 斐波那契數(shù)列的遞歸寫(xiě)法* 核心：一個(gè)小的解決終點(diǎn)，然后大的問(wèn)題可以循環(huán)在小問(wèn)題上解決* @param n* @return*/ long F(int n){if (n<=1) return n;return F(n-1)+F(n-2); }/*** 斐波那契數(shù)列的遞推寫(xiě)法* @param n* @return*/ long F1(int n){if (n<=1) return n;long fn = 0;long fn_1 = 1;long fn_2 = 0;for (int i = 2; i <= n; i++) {fn = fn_1 + fn_2;fn_2 = fn_1;fn_1 = fn;}return fn; }

可以看到，遞歸寫(xiě)法簡(jiǎn)單優(yōu)美，省去考慮很多邊界條件的時(shí)間。當(dāng)然，遞歸算法會(huì)保存很多的臨時(shí)數(shù)據(jù)，類似于堆棧的過(guò)程，如果棧深太深，就會(huì)造成內(nèi)存用盡，程序崩潰的現(xiàn)象。Java為每個(gè)線程分配了棧大小，如果棧大小溢出，就會(huì)報(bào)錯(cuò)，這時(shí)候還是選擇遞推好一點(diǎn)。

觀察下面的執(zhí)行過(guò)程也會(huì)發(fā)現(xiàn)，本程序并沒(méi)有保存每次的運(yùn)算結(jié)果，第三行的F(7)就執(zhí)行了兩次，下層的F(1),F(2)的次數(shù)更是指數(shù)級(jí)增長(zhǎng)。這也是本程序的一個(gè)弊端。

斐波那契執(zhí)行過(guò)程：

階乘

遞歸思想：n! = n * (n-1)! (直接看公式吧)

首先分析數(shù)列的遞歸表達(dá)式：

f(n)={1,f(n?1)?n,n<= 1n>1

代碼如下:

long factorial(int n){if (n <=1) return 1;return j(n-1)*n; }

執(zhí)行過(guò)程如下：

倒序輸出一個(gè)正整數(shù)

例如給出正整數(shù) n=12345，希望以各位數(shù)的逆序形式輸出，即輸出54321。

遞歸思想：首先輸出這個(gè)數(shù)的個(gè)位數(shù)，然后再輸出前面數(shù)字的個(gè)位數(shù)，直到之前沒(méi)數(shù)字。

首先分析數(shù)列的遞歸表達(dá)式：

f(n)={print(n%10),print(n%10);f(n/10),n< 10n>=10

代碼如下:

/*** 倒序輸出正整數(shù)的各位數(shù)* @param n*/ void printDigit(int n){System.out.print(n%10);if (n > 10){printDigit(n/10);} }

漢諾塔

超經(jīng)典了的遞歸解決問(wèn)題了：

法國(guó)數(shù)學(xué)家愛(ài)德華·盧卡斯曾編寫(xiě)過(guò)一個(gè)印度的古老傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

數(shù)學(xué)描述就是：

有三根桿子X(jué)，Y，Z。X桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至Y桿：
1. 每次只能移動(dòng)一個(gè)圓盤；
2. 大盤不能疊在小盤上面。

遞歸思想：
1. 將X桿上的n-1個(gè)圓盤都移到空閑的Z桿上，并且滿足上面的所有條件
2. 將X桿上的第n個(gè)圓盤移到Y(jié)上
3. 剩下問(wèn)題就是將Z桿上的n-1個(gè)圓盤移動(dòng)到Y(jié)上了

公式描述有點(diǎn)麻煩，用語(yǔ)言描述下吧：
1. 以Y桿為中介，將前n-1個(gè)圓盤從X桿挪到Z桿上(本身就是一個(gè)n-1的漢諾塔問(wèn)題了！)
2. 將第n個(gè)圓盤移動(dòng)到Y(jié)桿上
3. 以X桿為中介，將Z桿上的n-1個(gè)圓盤移到Y(jié)桿上(本身就是一個(gè)n-1的漢諾塔問(wèn)題了！)

代碼如下：

/*** 漢諾塔* 有柱子 x z y，最終將x上的n個(gè)圓盤借助z移動(dòng)到y(tǒng)上* 遞歸思想：* 1.將x上的n-1個(gè)放入到z上，借助y* 2.將x上的n圓盤放到y(tǒng)上* 3.將z上的n-1個(gè)圓盤放入y* @param n* @param from* @param tmp* @param to*/ void hanoi(int n,char from,char tmp,char to){if (n>0) {hanoi(n - 1, from, to, tmp);System.out.println("take " + n + " from " + from + " to " + to);hanoi(n - 1, tmp, from, to);} }

執(zhí)行過(guò)程：

如果一秒鐘移動(dòng)一次，世界毀滅需要多長(zhǎng)時(shí)間呢？5845.54億年以上，而地球存在至今不過(guò)45億年，地球現(xiàn)在還是很安全的。

排列問(wèn)題

輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來(lái)的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。

遞歸思想：
假如針對(duì)abc的排列，可以分成 (1)以a開(kāi)頭，加上bc的排列 (2)以b開(kāi)頭，加上ac的排列 (3)以c開(kāi)頭，加上ab的排列

/*** 產(chǎn)生排列組合的遞歸寫(xiě)法* @param t 數(shù)組* @param k 起始排列值* @param n 數(shù)組長(zhǎng)度*/ void pai(int[] t, int k, int n){if (k == n-1){//輸出這個(gè)排列for (int i = 0; i < n; i++) {System.out.print(t[i] + " ");}System.out.println();}else {for (int i = k; i < n; i++) {int tmp = t[i]; t[i] = t[k]; t[k] = tmp;//一次挑選n個(gè)字母中的一個(gè),和前位置替換pai(t, k+1, n); //再對(duì)其余的n-1個(gè)字母一次挑選tmp = t[i]; t[i] = t[k]; t[k] = tmp; //再換回來(lái)}} }

本題用遞歸算法很巧妙，省去了用普通方法時(shí)保存數(shù)據(jù)狀態(tài)的繁瑣操作！

總結(jié)

以上是生活随笔為你收集整理的递归整理及几个经典题目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。