java break递归_【Java】递归总结
摘要：
大師 L. Peter Deutsch 說(shuō)過(guò)：To Iterate is Human, to Recurse, Divine.中文譯為：人理解迭代，神理解遞歸。毋庸置疑地，遞歸確實(shí)是一個(gè)奇妙的思維方式。對(duì)一些簡(jiǎn)單的遞歸問(wèn)題，我們總是驚嘆于遞歸描述問(wèn)題的能力和編寫代碼的簡(jiǎn)潔，但要想真正領(lǐng)悟遞歸的精髓、靈活地運(yùn)用遞歸思想來(lái)解決問(wèn)題卻并不是一件容易的事情。本文剖析了遞歸的思想內(nèi)涵，分析了遞歸與循環(huán)的聯(lián)系與區(qū)別，給出了遞歸的應(yīng)用場(chǎng)景和一些典型應(yīng)用，并利用遞歸和非遞歸的方式解決了包括階乘、斐波那契數(shù)列、漢諾塔、楊輝三角的存取、字符串回文判斷、字符串全排列、二分查找、樹的深度求解在內(nèi)的八個(gè)經(jīng)典問(wèn)題。
版權(quán)聲明：
友情提示：
若讀者需要本博文相關(guān)完整代碼，請(qǐng)移步我的Github自行獲取，項(xiàng)目名為 SwordtoOffer，鏈接地址為：https://github.com/githubofrico/SwordtoOffer。
一. 引子
大師 L. Peter Deutsch 說(shuō)過(guò)：To Iterate is Human, to Recurse, Divine.中文譯為：人理解迭代，神理解遞歸。毋庸置疑地，遞歸確實(shí)是一個(gè)奇妙的思維方式。對(duì)一些簡(jiǎn)單的遞歸問(wèn)題，我們總是驚嘆于遞歸描述問(wèn)題的能力和編寫代碼的簡(jiǎn)潔，但要想真正領(lǐng)悟遞歸的精髓、靈活地運(yùn)用遞歸思想來(lái)解決問(wèn)題卻并不是一件容易的事情。在正式介紹遞歸之前，我們首先引用知乎用戶李繼剛(https://www.zhihu.com/question/20507130/answer/15551917)對(duì)遞歸和循環(huán)的生動(dòng)解釋：
遞歸：你打開面前這扇門，看到屋里面還有一扇門。你走過(guò)去，發(fā)現(xiàn)手中的鑰匙還可以打開它，你推開門，發(fā)現(xiàn)里面還有一扇門，你繼續(xù)打開它。若干次之后，你打開面前的門后，發(fā)現(xiàn)只有一間屋子，沒(méi)有門了。然后，你開始原路返回，每走回一間屋子，你數(shù)一次，走到入口的時(shí)候，你可以回答出你到底用這你把鑰匙打開了幾扇門。
循環(huán)：你打開面前這扇門，看到屋里面還有一扇門。你走過(guò)去，發(fā)現(xiàn)手中的鑰匙還可以打開它，你推開門，發(fā)現(xiàn)里面還有一扇門(若前面兩扇門都一樣，那么這扇門和前兩扇門也一樣；如果第二扇門比第一扇門小，那么這扇門也比第二扇門小，你繼續(xù)打開這扇門，一直這樣繼續(xù)下去直到打開所有的門。但是，入口處的人始終等不到你回去告訴他答案。
上面的比喻形象地闡述了遞歸與循環(huán)的內(nèi)涵，那么我們來(lái)思考以下幾個(gè)問(wèn)題：
什么是遞歸呢？
遞歸的精髓(思想)是什么？
遞歸和循環(huán)的區(qū)別是什么？
什么時(shí)候該用遞歸？
使用遞歸需要注意哪些問(wèn)題？
遞歸思想解決了哪些經(jīng)典的問(wèn)題？
這些問(wèn)題正是筆者準(zhǔn)備在本文中詳細(xì)闡述的問(wèn)題。
二. 遞歸的內(nèi)涵
1、定義 (什么是遞歸？)
在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸(Recursion)是指在函數(shù)的定義中使用函數(shù)自身的方法。實(shí)際上，遞歸，顧名思義，其包含了兩個(gè)意思：遞 和 歸，這正是遞歸思想的精華所在。
2、遞歸思想的內(nèi)涵(遞歸的精髓是什么？)
正如上面所描述的場(chǎng)景，遞歸就是有去(遞去)有回(歸來(lái))，如下圖所示。“有去”是指：遞歸問(wèn)題必須可以分解為若干個(gè)規(guī)模較小，與原問(wèn)題形式相同的子問(wèn)題，這些子問(wèn)題可以用相同的解題思路來(lái)解決，就像上面例子中的鑰匙可以打開后面所有門上的鎖一樣；“有回”是指 : 這些問(wèn)題的演化過(guò)程是一個(gè)從大到小，由近及遠(yuǎn)的過(guò)程，并且會(huì)有一個(gè)明確的終點(diǎn)(臨界點(diǎn))，一旦到達(dá)了這個(gè)臨界點(diǎn)，就不用再往更小、更遠(yuǎn)的地方走下去。最后，從這個(gè)臨界點(diǎn)開始，原路返回到原點(diǎn)，原問(wèn)題解決。
更直接地說(shuō)，遞歸的基本思想就是把規(guī)模大的問(wèn)題轉(zhuǎn)化為規(guī)模小的相似的子問(wèn)題來(lái)解決。特別地，在函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法往往是同一個(gè)方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況，這也正是遞歸的定義所在。格外重要的是，這個(gè)解決問(wèn)題的函數(shù)必須有明確的結(jié)束條件，否則就會(huì)導(dǎo)致無(wú)限遞歸的情況。
3、用歸納法來(lái)理解遞歸
數(shù)學(xué)都不差的我們，第一反應(yīng)就是遞歸在數(shù)學(xué)上的模型是什么，畢竟我們對(duì)于問(wèn)題進(jìn)行數(shù)學(xué)建模比起代碼建模拿手多了。觀察遞歸，我們會(huì)發(fā)現(xiàn)，遞歸的數(shù)學(xué)模型其實(shí)就是 數(shù)學(xué)歸納法，這個(gè)在高中的數(shù)列里面是最常用的了，下面回憶一下數(shù)學(xué)歸納法。
數(shù)學(xué)歸納法適用于將解決的原問(wèn)題轉(zhuǎn)化為解決它的子問(wèn)題，而它的子問(wèn)題又變成子問(wèn)題的子問(wèn)題，而且我們發(fā)現(xiàn)這些問(wèn)題其實(shí)都是一個(gè)模型，也就是說(shuō)存在相同的邏輯歸納處理項(xiàng)。當(dāng)然有一個(gè)是例外的，也就是歸納結(jié)束的那一個(gè)處理方法不適用于我們的歸納處理項(xiàng)，當(dāng)然也不能適用，否則我們就無(wú)窮歸納了。總的來(lái)說(shuō)，歸納法主要包含以下三個(gè)關(guān)鍵要素：
步進(jìn)表達(dá)式：問(wèn)題蛻變成子問(wèn)題的表達(dá)式
結(jié)束條件：什么時(shí)候可以不再使用步進(jìn)表達(dá)式
直接求解表達(dá)式：在結(jié)束條件下能夠直接計(jì)算返回值的表達(dá)式
事實(shí)上，這也正是某些數(shù)學(xué)中的數(shù)列問(wèn)題在利用編程的方式去解決時(shí)可以使用遞歸的原因，比如著名的斐波那契數(shù)列問(wèn)題。
4、遞歸的三要素
在我們了解了遞歸的基本思想及其數(shù)學(xué)模型之后，我們?nèi)绾尾拍軐懗鲆粋€(gè)漂亮的遞歸程序呢？筆者認(rèn)為主要是把握好如下三個(gè)方面：
1、明確遞歸終止條件；
2、給出遞歸終止時(shí)的處理辦法；
3、提取重復(fù)的邏輯，縮小問(wèn)題規(guī)模。
1). 明確遞歸終止條件
我們知道，遞歸就是有去有回，既然這樣，那么必然應(yīng)該有一個(gè)明確的臨界點(diǎn)，程序一旦到達(dá)了這個(gè)臨界點(diǎn)，就不用繼續(xù)往下遞去而是開始實(shí)實(shí)在在的歸來(lái)。換句話說(shuō)，該臨界點(diǎn)就是一種簡(jiǎn)單情境，可以防止無(wú)限遞歸。
2). 給出遞歸終止時(shí)的處理辦法
我們剛剛說(shuō)到，在遞歸的臨界點(diǎn)存在一種簡(jiǎn)單情境，在這種簡(jiǎn)單情境下，我們應(yīng)該直接給出問(wèn)題的解決方案。一般地，在這種情境下，問(wèn)題的解決方案是直觀的、容易的。
3). 提取重復(fù)的邏輯，縮小問(wèn)題規(guī)模*
我們?cè)陉U述遞歸思想內(nèi)涵時(shí)談到，遞歸問(wèn)題必須可以分解為若干個(gè)規(guī)模較小、與原問(wèn)題形式相同的子問(wèn)題，這些子問(wèn)題可以用相同的解題思路來(lái)解決。從程序?qū)崿F(xiàn)的角度而言，我們需要抽象出一個(gè)干凈利落的重復(fù)的邏輯，以便使用相同的方式解決子問(wèn)題。
5、遞歸算法的編程模型
在我們明確遞歸算法設(shè)計(jì)三要素后，接下來(lái)就需要著手開始編寫具體的算法了。在編寫算法時(shí)，不失一般性，我們給出兩種典型的遞歸算法設(shè)計(jì)模型，如下所示。
模型一： 在遞去的過(guò)程中解決問(wèn)題
function recursion(大規(guī)模){
if (end_condition){ // 明確的遞歸終止條件
end; // 簡(jiǎn)單情景
}else{ // 在將問(wèn)題轉(zhuǎn)換為子問(wèn)題的每一步，解決該步中剩余部分的問(wèn)題
solve; // 遞去
recursion(小規(guī)模); // 遞到最深處后，不斷地歸來(lái)
}
}
模型二： 在歸來(lái)的過(guò)程中解決問(wèn)題
function recursion(大規(guī)模){
if (end_condition){ // 明確的遞歸終止條件
end; // 簡(jiǎn)單情景
}else{ // 先將問(wèn)題全部描述展開，再由盡頭“返回”依次解決每步中剩余部分的問(wèn)題
recursion(小規(guī)模); // 遞去
solve; // 歸來(lái)
}
}
6、遞歸的應(yīng)用場(chǎng)景
在我們實(shí)際學(xué)習(xí)工作中，遞歸算法一般用于解決三類問(wèn)題：
(1). 問(wèn)題的定義是按遞歸定義的(Fibonacci函數(shù)，階乘，…)；
(2). 問(wèn)題的解法是遞歸的(有些問(wèn)題只能使用遞歸方法來(lái)解決，例如，漢諾塔問(wèn)題，…)；
(3). 數(shù)據(jù)結(jié)構(gòu)是遞歸的(鏈表、樹等的操作，包括樹的遍歷，樹的深度，…)。
在下文我們將給出遞歸算法的一些經(jīng)典應(yīng)用案例，這些案例基本都屬于第三種類型問(wèn)題的范疇。
三. 遞歸與循環(huán)
遞歸與循環(huán)是兩種不同的解決問(wèn)題的典型思路。遞歸通常很直白地描述了一個(gè)問(wèn)題的求解過(guò)程，因此也是最容易被想到解決方式。循環(huán)其實(shí)和遞歸具有相同的特性，即做重復(fù)任務(wù)，但有時(shí)使用循環(huán)的算法并不會(huì)那么清晰地描述解決問(wèn)題步驟。單從算法設(shè)計(jì)上看，遞歸和循環(huán)并無(wú)優(yōu)劣之別。然而，在實(shí)際開發(fā)中，因?yàn)楹瘮?shù)調(diào)用的開銷，遞歸常常會(huì)帶來(lái)性能問(wèn)題，特別是在求解規(guī)模不確定的情況下；而循環(huán)因?yàn)闆](méi)有函數(shù)調(diào)用開銷，所以效率會(huì)比遞歸高。遞歸求解方式和循環(huán)求解方式往往可以互換，也就是說(shuō)，如果用到遞歸的地方可以很方便使用循環(huán)替換，而不影響程序的閱讀，那么替換成循環(huán)往往是好的。問(wèn)題的遞歸實(shí)現(xiàn)轉(zhuǎn)換成非遞歸實(shí)現(xiàn)一般需要兩步工作：
(1). 自己建立“堆棧(一些局部變量)”來(lái)保存這些內(nèi)容以便代替系統(tǒng)棧，比如樹的三種非遞歸遍歷方式；
(2). 把對(duì)遞歸的調(diào)用轉(zhuǎn)變?yōu)閷?duì)循環(huán)處理。
特別地，在下文中我們將給出遞歸算法的一些經(jīng)典應(yīng)用案例，對(duì)于這些案例的實(shí)現(xiàn)，我們一般會(huì)給出遞歸和非遞歸兩種解決方案，以便讀者體會(huì)。
四. 經(jīng)典遞歸問(wèn)題實(shí)戰(zhàn)
第一類問(wèn)題：問(wèn)題的定義是按遞歸定義的
(1). 階乘
/**
* Title: 階乘的實(shí)現(xiàn)
* Description:
* 遞歸解法
* 非遞歸解法
*@author rico
*/
public class Factorial {
/**
*@description 階乘的遞歸實(shí)現(xiàn)
*@author rico
*@created 2017年5月10日 下午8:45:48
*@param n
*@return
*/
public static long f(int n){
if(n == 1) // 遞歸終止條件
return 1; // 簡(jiǎn)單情景
return n*f(n-1); // 相同重復(fù)邏輯，縮小問(wèn)題的規(guī)模
}
--------------------------------我是分割線-------------------------------------
/**
*@description 階乘的非遞歸實(shí)現(xiàn)
*@author rico
*@created 2017年5月10日 下午8:46:43
*@param n
*@return
*/
public static long f_loop(int n) {
long result = n;
while (n > 1) {
n--;
result = result * n;
}
return result;
}
}1
(2). 斐波納契數(shù)列
/**
* Title: 斐波納契數(shù)列
*
* Description: 斐波納契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、……
* 在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F1=1，Fn=F(n-1)+F(n-2)(n>=2，n∈N*)。
*
* 兩種遞歸解法：經(jīng)典解法和優(yōu)化解法
* 兩種非遞歸解法：遞推法和數(shù)組法
*
* @author rico
*/
public class FibonacciSequence {
/**
*@description 經(jīng)典遞歸法求解
*
* 斐波那契數(shù)列如下：
*
* 1,1,2,3,5,8,13,21,34,...
*
* *那么，計(jì)算fib(5)時(shí)，需要計(jì)算1次fib(4),2次fib(3),3次fib(2)，調(diào)用了2次fib(1)*，即：
*
* fib(5) = fib(4) + fib(3)
*
* fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
*
* fib(3) = fib(2) + fib(1)
*
* 這里面包含了許多重復(fù)計(jì)算，而實(shí)際上我們只需計(jì)算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
* 后面的optimizeFibonacci函數(shù)進(jìn)行了優(yōu)化，使時(shí)間復(fù)雜度降到了O(n).
*
*@author rico
*@created 2017年5月10日 下午12:00:42
*@param n
*@return
*/
public static int fibonacci(int n) {
if (n == 1 || n == 2) { // 遞歸終止條件
return 1; // 簡(jiǎn)單情景
}
return fibonacci(n - 1) + fibonacci(n - 2); // 相同重復(fù)邏輯，縮小問(wèn)題的規(guī)模
}
——————————–我是分割線————————————-
/**
* @description 對(duì)經(jīng)典遞歸法的優(yōu)化
*
* 斐波那契數(shù)列如下：
*
* 1,1,2,3,5,8,13,21,34,...
*
* 那么，我們可以這樣看：fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5
*
* 也就是說(shuō)，以1,1開頭的斐波那契數(shù)列的第五項(xiàng)正是以1,2開頭的斐波那契數(shù)列的第四項(xiàng)，
* 而以1,2開頭的斐波那契數(shù)列的第四項(xiàng)也正是以2,3開頭的斐波那契數(shù)列的第三項(xiàng)，
* 更直接地，我們就可以一步到位：fib(2,3,3) = 2 + 3 = 5,計(jì)算結(jié)束。
*
* 注意，前兩個(gè)參數(shù)是數(shù)列的開頭兩項(xiàng)，第三個(gè)參數(shù)是我們想求的以前兩個(gè)參數(shù)開頭的數(shù)列的第幾項(xiàng)。
*
* 時(shí)間復(fù)雜度：O(n)
*
* @author rico
* @param first 數(shù)列的第一項(xiàng)
* @param second 數(shù)列的第二項(xiàng)
* @param n 目標(biāo)項(xiàng)
* @return
*/
public static int optimizeFibonacci(int first, int second, int n) {
if (n > 0) {
if(n == 1){ // 遞歸終止條件
return first; // 簡(jiǎn)單情景
}else if(n == 2){ // 遞歸終止條件
return second; // 簡(jiǎn)單情景
}else if (n == 3) { // 遞歸終止條件
return first + second; // 簡(jiǎn)單情景
}
return optimizeFibonacci(second, first + second, n - 1); // 相同重復(fù)邏輯，縮小問(wèn)題規(guī)模
}
return -1;
}
--------------------------------我是分割線-------------------------------------
/**
*@description 非遞歸解法：有去無(wú)回
*@author rico
*@created 2017年5月10日 下午12:03:04
*@param n
*@return
*/
public static int fibonacci_loop(int n) {
if (n == 1 || n == 2) {
return 1;
}
int result = -1;
int first = 1; // 自己維護(hù)的"棧",以便狀態(tài)回溯
int second = 1; // 自己維護(hù)的"棧",以便狀態(tài)回溯
for (int i = 3; i <= n; i++) { // 循環(huán)
result = first + second;
first = second;
second = result;
}
return result;
}
--------------------------------我是分割線-------------------------------------
/**
*@description 使用數(shù)組存儲(chǔ)斐波那契數(shù)列
*@author rico
*@param n
*@return
*/
public static int fibonacci_array(int n) {
if (n > 0) {
int[] arr = new int[n]; // 使用臨時(shí)數(shù)組存儲(chǔ)斐波納契數(shù)列
arr[0] = arr[1] = 1;
for (int i = 2; i < n; i++) { // 為臨時(shí)數(shù)組賦值
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n - 1];
}
return -1;
}
}
(3). 楊輝三角的取值
/**
* @description 遞歸獲取楊輝三角指定行、列(從0開始)的值
* 注意：與是否創(chuàng)建楊輝三角無(wú)關(guān)
* @author rico
* @x 指定行
* @y 指定列
*/
/**
* Title: 楊輝三角形又稱Pascal三角形，它的第i+1行是(a+b)i的展開式的系數(shù)。
* 它的一個(gè)重要性質(zhì)是：三角形中的每個(gè)數(shù)字等于它兩肩上的數(shù)字相加。
*
* 例如，下面給出了楊輝三角形的前4行：
* 1
* 1 1
* 1 2 1
* 1 3 3 1
*@description 遞歸獲取楊輝三角指定行、列(從0開始)的值
* 注意：與是否創(chuàng)建楊輝三角無(wú)關(guān)
*@author rico
*@x 指定行
*@y 指定列
*/
public static int getValue(int x, int y) {
if(y <= x && y >= 0){
if(y == 0 || x == y){ // 遞歸終止條件
return 1;
}else{
// 遞歸調(diào)用，縮小問(wèn)題的規(guī)模
return getValue(x-1, y-1) + getValue(x-1, y);
}
}
return -1;
}
}
(4). 回文字符串的判斷
/**
* Title: 回文字符串的判斷
* Description: 回文字符串就是正讀倒讀都一樣的字符串。如”98789”, “abccba”都是回文字符串
*
* 兩種解法：
* 遞歸判斷；
* 循環(huán)判斷；
*
* @author rico
*/
public class PalindromeString {
/**
*@description 遞歸判斷一個(gè)字符串是否是回文字符串
*@author rico
*@created 2017年5月10日 下午5:45:50
*@param s
*@return
*/
public static boolean isPalindromeString_recursive(String s){
int start = 0;
int end = s.length()-1;
if(end > start){ // 遞歸終止條件:兩個(gè)指針相向移動(dòng)，當(dāng)start超過(guò)end時(shí)，完成判斷
if(s.charAt(start) != s.charAt(end)){
return false;
}else{
// 遞歸調(diào)用，縮小問(wèn)題的規(guī)模
return isPalindromeString_recursive(s.substring(start+1).substring(0, end-1));
}
}
return true;
}
--------------------------------我是分割線-------------------------------------
/**
*@description 循環(huán)判斷回文字符串
*@author rico
*@param s
*@return
*/
public static boolean isPalindromeString_loop(String s){
char[] str = s.toCharArray();
int start = 0;
int end = str.length-1;
while(end > start){ // 循環(huán)終止條件:兩個(gè)指針相向移動(dòng)，當(dāng)start超過(guò)end時(shí)，完成判斷
if(str[end] != str[start]){
return false;
}else{
end --;
start ++;
}
}
return true;
}
}
(5). 字符串全排列
遞歸解法
/**
* @description 從字符串?dāng)?shù)組中每次選取一個(gè)元素，作為結(jié)果中的第一個(gè)元素;然后，對(duì)剩余的元素全排列
* @author rico
* @param s
* 字符數(shù)組
* @param from
* 起始下標(biāo)
* @param to
* 終止下標(biāo)
*/
public static void getStringPermutations3(char[] s, int from, int to) {
if (s != null && to >= from && to < s.length && from >= 0) { // 邊界條件檢查
if (from == to) { // 遞歸終止條件
System.out.println(s); // 打印結(jié)果
} else {
for (int i = from; i <= to; i++) {
swap(s, i, from); // 交換前綴,作為結(jié)果中的第一個(gè)元素，然后對(duì)剩余的元素全排列
getStringPermutations3(s, from + 1, to); // 遞歸調(diào)用，縮小問(wèn)題的規(guī)模
swap(s, from, i); // 換回前綴，復(fù)原字符數(shù)組
}
}
}
}
/**
*@description 對(duì)字符數(shù)組中的制定字符進(jìn)行交換
*@author rico
*@param s
*@param from
*@param to
*/
public static void swap(char[] s, int from, int to) {
char temp = s[from];
s[from] = s[to];
s[to] = temp;
}
非遞歸解法(字典序全排列)
/**
* Title: 字符串全排列非遞歸算法(字典序全排列)
* Description: 字典序全排列，其基本思想是：
* 先對(duì)需要求排列的字符串進(jìn)行字典排序，即得到全排列中最小的排列.
* 然后,找到一個(gè)比它大的最小的全排列，一直重復(fù)這一步直到找到最大值,即字典排序的逆序列.
*
* 不需要關(guān)心字符串長(zhǎng)度
*
* @author rico
*/
public class StringPermutationsLoop {
/**
* @description 字典序全排列
*
* 設(shè)一個(gè)字符串(字符數(shù)組)的全排列有n個(gè)，分別是A1,A2,A3,...,An
*
* 1. 找到最小的排列 Ai
* 2. 找到一個(gè)比Ai大的最小的后繼排列Ai+1
* 3. 重復(fù)上一步直到?jīng)]有這樣的后繼
*
* 重點(diǎn)就是如何找到一個(gè)排列的直接后繼:
* 對(duì)于字符串(字符數(shù)組)a0a1a2……an,
* 1. 從an到a0尋找第一次出現(xiàn)的升序排列的兩個(gè)字符(即ai < ai+1),那么ai+1是一個(gè)極值，因?yàn)閍i+1之后的字符為降序排列，記 top=i+1;
* 2. 從top處(包括top)開始查找比ai大的最小的值aj，記 minMax = j;
* 3. 交換minMax處和top-1處的字符;
* 4. 翻轉(zhuǎn)top之后的字符(包括top)，即得到一個(gè)排列的直接后繼排列
*
* @author rico
* @param s
* 字符數(shù)組
* @param from
* 起始下標(biāo)
* @param to
* 終止下標(biāo)
*/
public static void getStringPermutations4(char[] s, int from, int to) {
Arrays.sort(s,from,to+1); // 對(duì)字符數(shù)組的所有元素進(jìn)行升序排列，即得到最小排列
System.out.println(s);
char[] descendArr = getMaxPermutation(s, from, to); // 得到最大排列,即最小排列的逆序列
while (!Arrays.equals(s, descendArr)) { // 循環(huán)終止條件：迭代至最大排列
if (s != null && to >= from && to < s.length && from >= 0) { // 邊界條件檢查
int top = getExtremum(s, from, to); // 找到序列的極值
int minMax = getMinMax(s, top, to); // 從top處(包括top)查找比s[top-1]大的最小值所在的位置
swap(s, top - 1, minMax); // 交換minMax處和top-1處的字符
s = reverse(s, top, to); // 翻轉(zhuǎn)top之后的字符
System.out.println(s);
}
}
}
/**
*@description 對(duì)字符數(shù)組中的制定字符進(jìn)行交換
*@author rico
*@param s
*@param from
*@param to
*/
public static void swap(char[] s, int from, int to) {
char temp = s[from];
s[from] = s[to];
s[to] = temp;
}
/**
*@description 獲取序列的極值
*@author rico
*@param s 序列
*@param from 起始下標(biāo)
*@param to 終止下標(biāo)
*@return
*/
public static int getExtremum(char[] s, int from, int to) {
int index = 0;
for (int i = to; i > from; i--) {
if (s[i] > s[i - 1]) {
index = i;
break;
}
}
return index;
}
/**
*@description 從top處查找比s[top-1]大的最小值所在的位置
*@author rico
*@created 2017年5月10日 上午9:21:13
*@param s
*@param top 極大值所在位置
*@param to
*@return
*/
public static int getMinMax(char[] s, int top, int to) {
int index = top;
char base = s[top-1];
char temp = s[top];
for (int i = top + 1; i <= to; i++) {
if (s[i] > base && s[i] < temp) {
temp = s[i];
index = i;
}
continue;
}
return index;
}
/**
*@description 翻轉(zhuǎn)top(包括top)后的序列
*@author rico
*@param s
*@param from
*@param to
*@return
*/
public static char[] reverse(char[] s, int top, int to) {
char temp;
while(top < to){
temp = s[top];
s[top] = s[to];
s[to] = temp;
top ++;
to --;
}
return s;
}
/**
*@description 根據(jù)最小排列得到最大排列
*@author rico
*@param s 最小排列
*@param from 起始下標(biāo)
*@param to 終止下標(biāo)
*@return
*/
public static char[] getMaxPermutation(char[] s, int from, int to) {
//將最小排列復(fù)制到一個(gè)新的數(shù)組中
char[] dsc = Arrays.copyOfRange(s, 0, s.length);
int first = from;
int end = to;
while(end > first){ // 循環(huán)終止條件
char temp = dsc[first];
dsc[first] = dsc[end];
dsc[end] = temp;
first ++;
end --;
}
return dsc;
}
(6). 二分查找
/**
* @description 二分查找的遞歸實(shí)現(xiàn)
* @author rico
* @param array 目標(biāo)數(shù)組
* @param low 左邊界
* @param high 右邊界
* @param target 目標(biāo)值
* @return 目標(biāo)值所在位置
*/
public static int binarySearch(int[] array, int low, int high, int target) {
//遞歸終止條件
if(low <= high){
int mid = (low + high) >> 1;
if(array[mid] == target){
return mid + 1; // 返回目標(biāo)值的位置，從1開始
}else if(array[mid] > target){
// 由于array[mid]不是目標(biāo)值，因此再次遞歸搜索時(shí)，可以將其排除
return binarySearch(array, low, mid-1, target);
}else{
// 由于array[mid]不是目標(biāo)值，因此再次遞歸搜索時(shí)，可以將其排除
return binarySearch(array, mid+1, high, target);
}
}
return -1; //表示沒(méi)有搜索到
}
--------------------------------我是分割線-------------------------------------
/**
*@description 二分查找的非遞歸實(shí)現(xiàn)
*@author rico
*@param array 目標(biāo)數(shù)組
*@param low 左邊界
*@param high 右邊界
*@param target 目標(biāo)值
*@return 目標(biāo)值所在位置
*/
public static int binarySearchNoRecursive(int[] array, int low, int high, int target) {
// 循環(huán)
while (low <= high) {
int mid = (low + high) >> 1;
if (array[mid] == target) {
return mid + 1; // 返回目標(biāo)值的位置，從1開始
} else if (array[mid] > target) {
// 由于array[mid]不是目標(biāo)值，因此再次遞歸搜索時(shí)，可以將其排除
high = mid -1;
} else {
// 由于array[mid]不是目標(biāo)值，因此再次遞歸搜索時(shí)，可以將其排除
low = mid + 1;
}
}
return -1; //表示沒(méi)有搜索到
}
第二類問(wèn)題：問(wèn)題解法按遞歸算法實(shí)現(xiàn)
(1). 漢諾塔問(wèn)題
/**
* Title: 漢諾塔問(wèn)題
* Description:古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有64個(gè)盤子，盤子大小不等，大的在下，小的在上。
* 有一個(gè)和尚想把這64個(gè)盤子從A座移到C座，但每次只能允許移動(dòng)一個(gè)盤子，并且在移動(dòng)過(guò)程中，3個(gè)座上的盤子始終保持大盤在下，
* 小盤在上。在移動(dòng)過(guò)程中可以利用B座。要求輸入層數(shù)，運(yùn)算后輸出每步是如何移動(dòng)的。
*
* @author rico
*/
public class HanoiTower {
/**
*@description 在程序中，我們把最上面的盤子稱為第一個(gè)盤子，把最下面的盤子稱為第N個(gè)盤子
*@author rico
*@param level：盤子的個(gè)數(shù)
*@param from 盤子的初始地址
*@param inter 轉(zhuǎn)移盤子時(shí)用于中轉(zhuǎn)
*@param to 盤子的目的地址
*/
public static void moveDish(int level, char from, char inter, char to) {
if (level == 1) { // 遞歸終止條件
System.out.println("從" + from + " 移動(dòng)盤子" + level + " 號(hào)到" + to);
} else {
// 遞歸調(diào)用：將level-1個(gè)盤子從from移到inter(不是一次性移動(dòng)，每次只能移動(dòng)一個(gè)盤子,其中to用于周轉(zhuǎn))
moveDish(level - 1, from, to, inter); // 遞歸調(diào)用，縮小問(wèn)題的規(guī)模
// 將第level個(gè)盤子從A座移到C座
System.out.println("從" + from + " 移動(dòng)盤子" + level + " 號(hào)到" + to);
// 遞歸調(diào)用：將level-1個(gè)盤子從inter移到to,from 用于周轉(zhuǎn)
moveDish(level - 1, inter, from, to); // 遞歸調(diào)用，縮小問(wèn)題的規(guī)模
}
}
public static void main(String[] args) {
int nDisks = 30;
moveDish(nDisks, 'A', 'B', 'C');
}
第三類問(wèn)題：數(shù)據(jù)的結(jié)構(gòu)是按遞歸定義的
(1). 二叉樹深度
/**
* Title: 遞歸求解二叉樹的深度
* Description:
* @author rico
* @created 2017年5月8日 下午6:34:50
*/
public class BinaryTreeDepth {
/**
*@description 返回二叉數(shù)的深度
*@author rico
*@param t
*@return
*/
public static int getTreeDepth(Tree t) {
// 樹為空
if (t == null) // 遞歸終止條件
return 0;
int left = getTreeDepth(t.left); // 遞歸求左子樹深度，縮小問(wèn)題的規(guī)模
int right = getTreeDepth(t.left); // 遞歸求右子樹深度，縮小問(wèn)題的規(guī)模
return left > right ? left + 1 : right + 1;
}
}
(2). 二叉樹深度
/**
* @description 前序遍歷(遞歸)
* @author rico
* @created 2017年5月22日 下午3:06:11
* @param root
* @return
*/
public String preOrder(Node root) {
StringBuilder sb = new StringBuilder(); // 存到遞歸調(diào)用棧
if (root == null) { // 遞歸終止條件
return ""; // ji
}else { // 遞歸終止條件
sb.append(root.data + " "); // 前序遍歷當(dāng)前結(jié)點(diǎn)
sb.append(preOrder(root.left)); // 前序遍歷左子樹
sb.append(preOrder(root.right)); // 前序遍歷右子樹
return sb.toString();
}
}
總結(jié)
以上是生活随笔為你收集整理的java break递归_【Java】递归总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： java数据类型的站位_Java 数据类
- 下一篇： mysql四种事务级别_【MySQL 知