Java 中的遞歸

遞歸

遞歸一種通過調用某個方法來描述需要重複進行的操作。該方法的特點就是可以自己調用自己。

案例一

排隊的問題

在生活中，我們經常需要排隊。在排隊中，我們怎麼才能知道自己所排在第幾位呢？

我們也許會想到數自己前面有幾個人，這就是典型的疊代思想。就像是一個while循環，隻要前面還有沒數過的人，就不會停止。這種方式相對來說是比較直覺的，但是同樣也有局限性。比如在排隊時，遇到了轉彎，我們看不到前面的人怎麼辦呢？

有一個方法，我們可以通過詢問前面一個人他所處的位置。假設有A、B、C、D四個人，D詢問C所在的位置，C詢問B所在位置，B詢問A所在的位置。A知道自己排在第一位（他不需要再問别人了，這一個詢問的過程結束），然後告訴B，那B就知道自己在第二位；然後B告訴C，C也就知道了自己在第三位；最後C告訴D他在第三位時，D也就知道自己所在的位置了。這就是使用遞歸思想來分析問題——每個人都來回答一個問題，進而使這個問題多次重制（recur）。

這一點也是遞歸思想的精髓所在，遞歸方法涉及多個進行合作的單元，每個單元負責解決問題的一小部分。例如剛剛那個例子，每個人都像前詢問一個問題，最後每個人又向後回答一個問題，而不是由一個人來負責統計所有的人數。

疊代到遞歸的轉變

根據傳遞的長度length，列印出length個“ * ”

/**

疊代

*
@param length

*/

public void writeStars1(int length) {

for (int i = 0; i < length; i++) {
    System.out.print("*");
}
System.out.println();

}

public void writeStars2(int length) {

if (length == 0) {
    System.out.println();
} else {
    System.out.print("*");
    writeStars2(length - 1);
}

上面這兩個方法最終結果都是一樣的。不同的是，疊代好比是一個人來統計所有的人數。遞歸則是由每個人回答同一個問題，由于每個人所在的位置不同，所回答的結果也不相同。

遞歸方法的結構

public void writeStars3(int length) {

System.out.println("*");
writeStars3(length - 1);

我們看一下上面這段代碼，如果執行這段代碼，程式并不會停止，會一直在自己調用自己執行下去。這也就是我們可能會遇到的無窮遞歸（infinite recursion）。

遞歸方法有兩個重要的組成部分：一個基本情況（base case）和一個遞歸情況（recursive case）。

基本情況一種簡單到不需要遞歸調用就可以解決的情況。

遞歸情況一種需要把整個問題轉化成一個相同種類的，比較簡單的，而且可以通過遞歸調用來解決的問題的情況。

通過注釋來解釋基本情況和遞歸情況

if (length == 0) {
    // 基本情況
    System.out.println();
} else {
    // 遞歸情況
    System.out.print("*");
    writeStars2(length - 1);
}

案例二

我們有一個LinkedList集合，現在需要按照倒叙把集合的内容列印出來，列印完之後集合裡面不要有資料。

通過疊代實作

代碼

LinkedList list = new LinkedList<>();

list.add("a");

list.add("b");

list.add("c");

list.add("d");

list.add("e");

list.add("f");

System.out.println(list);

for (int i = list.size() - 1; i >= 0; i--) {

System.out.print(list.get(i) + " ");

list.clear();

System.out.println();

輸出結果

[a, b, c, d, e, f]

f e d c b a

[]

看到上面的結果，顯然是符合要求的。那我們如果使用遞歸，該怎麼實作呢？

通過遞歸實作

public static void main(String[] args) {

LinkedList<String> list = new LinkedList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
list.add("f");

System.out.println(list);

Iterator<String> iterator = list.iterator();
writeArray(iterator);

System.out.println();
System.out.println(list);

遞歸實作
@param iterator

private static void writeArray(Iterator iterator) {

// 如果疊代器中還有資料，才進行遞歸計算
if (iterator.hasNext()) {
    // 獲得目前指針的參數
    String next = iterator.next();
    // 删除目前指針
    iterator.remove();
    // 使用遞歸計算
    writeArray(iterator);
    System.out.print(next + " ");
}

由上述代碼可以看出，使用遞歸算法，也可以同樣得到結果，并且可以不使用for循環來完成任務。

調用棧

調用棧用來跟蹤所調用方法的順序的内部結構。

了解遞歸的底層機制，對于初學者來說是很有幫助的。我們先來分析下面這段代碼：

draw();
 draws();

private static void draw(){

System.out.println("在紙上畫了一幅畫");

private static void draws(){

draw();
draw();

我們來人工debug一下這段代碼。

程式首先進入main方法；

然後程式會停止執行main方法，轉而去執行draw方法，當程式執行完draw方法時，會回到main方法當中；

接着需要執行draws方法，draws方法又會去調用兩次draw方法。而此時位于頂端的方法則是我們正在執行的方法draw；

當我們執行draw時，回到了draws上面，執行完draws後，最終會回到main方法中；

調用一個方法我們就把它放在最上面的位置，這就是Java的調用棧（call stack）

了解了什麼是調用棧，則可以利用調用棧來分析剛剛那個遞歸倒叙是如何工作的了。

案例三

整數的密運算。Math.pow(x, y)可以進行x的y次幂運算。但是如果要通過遞歸該如何實作呢？

為求簡單，我們隻考慮整數的情況。也就是說我們不考慮負指數，因為它的結果不是整數。

在遞歸情況中，我們已知y > 0。我們至少需要再乘一個x：x的y次幂=x * x的y-1次幂（$x^y = x * x^z$）。由此我們可通過以下代碼實作。

System.out.println(Math.pow(3, 5));
System.out.println(pow(3, 5));

private static int pow(int x, int y) {

// 按照定義，任何整數的零次幂都是1
if (y == 0) {
    return 1;
} else {
    return x * pow(x, y - 1);
}

運算結果

243.0

案例四

我們在寫程式時，通常都會使用包含上下級結構的碼表，例如下面這個資料：

SysCode{scId='01', itemName='測試1', sort=1, fScId='null', cDesc='測試測試1'}

SysCode{scId='02', itemName='測試2', sort=1, fScId='01', cDesc='測試測試2'}

SysCode{scId='03', itemName='測試3', sort=3, fScId='01', cDesc='測試測試3'}

SysCode{scId='04', itemName='測試4', sort=2, fScId='01', cDesc='測試測試4'}

SysCode{scId='05', itemName='測試5', sort=1, fScId='03', cDesc='測試測試5'}

SysCode{scId='06', itemName='測試6', sort=2, fScId='03', cDesc='測試測試6'}

SysCode{scId='07', itemName='測試7', sort=2, fScId='null', cDesc='測試測試2'}

SysCode{scId='08', itemName='測試8', sort=1, fScId='07', cDesc='測試測試2'}

分析以上代碼，我們可以根據fScId封裝上下級

關系，首先在SysCode類中增加一個children集合來儲存子集。

使用遞歸建立子集
@param scId
@param list
@return

private List getSysCodeChildren(String scId, List list) {

List<SysCode> sysCodeList = new ArrayList<>();
list.forEach(e -> {
    if (null != e.getfScId() && e.getfScId().equals(scId)) {
        e.setChildren(getSysCodeChildren(e.getScId(), list));
        sysCodeList.add(e);
    }
});
return sysCodeList;

遞歸回溯

很多問題都可以通過系統地檢查各種可能性來求解。比如，一個迷宮得遊戲，要從入口找到出口，可以檢查每一條線路，直到找到可行的線路。

很多使用窮舉搜尋求解得問題都能夠用回溯法（backtracking）求解。回溯法是一種适宜用遞歸方式表示的問題求解方法。是以，這種方法也稱為遞歸回溯（recursive backtracking）。

（遞歸）回溯法一種搜尋問題解的通用算法，它先找出可能得候選解，一旦确定某個候選解不适合，就立刻放棄進一步嘗試（回溯）。

案例分析

移動線路問題

考慮一個标準的平面直角坐标系（x, y），假設從原點（0, 0）出發，可以進行以下三種移動方式：

向北移動（用“ N ”表示），每次移動縱坐标 +1；

向東移動（用“ E ”表示），每次移動橫坐标 +1；

向東北移動（用“ NE ”表示），每次縱坐标，橫坐标各 +1；

如上圖所示，從原點出發，會有三種不同的移動方式。現在定義一種移動路線問題：通過一系列移動，從原點到坐标（x, y）。例如，通過移動序列：N -> NE -> N 可以到達（1, 3）。

每個适用于回溯法解決的問題都具有包含問題所有可能解的解空間（solution space）。可以把解空間想象成一顆決策樹（decision tree）。對于我們要解決的移動線路問題來說，每次移動方案都是選擇的結果。

考慮從原點（0, 0）到（1, 2），所有可能的移動序号是：

N -> N -> E

N -> E -> N

N -> NE

E -> N -> N

NE -> N

用程式該如何找出這些解呢？對于大多數回溯問題，最終都會編寫兩個方法。一般會定義一個含有反應問題特性的參數的公有方法。另外會定義一個包含一些額外參數，執行實際回溯處理過程的私有方法。

因為要使用遞歸，是以需要确定基本情況和遞歸情況這兩個部分。回溯法通常包含兩種不通的基本情況。找到解時，停止回溯，這也是遞歸過程的一個基本情況。發現遇到死路的時候，停止繼續搜尋。

在回溯搜尋過程中，如果既沒有找到問題的解，也沒有進入死路，就需要繼續探索每一種可能的選擇。根據上述的分析，我們可以編寫以下僞代碼來解釋該回溯過程：

private static void explore(current(x, y), target(x, y)) {

if(一個解) {
    列印出解
} else if(不是死路) {
    explore(向N移動);
    explore(向E移動);
    explore(向NE移動);
}

在這個問題中，我們需要目前位置的x, y坐标和目标x, y的坐标。還要記錄每次移動的結果，用來形成最終的路徑報告。

我們可以通過對比目前移動的起點和終點是否比對，來驗證是否找到了解。對于是否進入死路這個問題，我們知道在移動的過程中，橫坐标和縱坐标隻會遞增，是以一旦目前位置的x坐标值大于目标位置的x坐标值，或者目前位置的y坐标值大于目标位置的y坐标值，就能知道在相應方向上移動距離超過了目标值，是以永遠不可能找到解，這時需要停止繼續搜尋。整合這些分析，我們可以得到以下代碼：

// 使用回溯法找到（1, 2）的所有線路
travel(1, 2);

反應問題特性的參數的公有方法
@param targetX ：x目标值
@param targetY ：y目标值

public static void travel(int targetX, int targetY) {

explore(targetX, targetY, 0, 0, "path: ");

執行實際回溯處理過程的私有方法
@param currX ：目前x目标值
@param currY ：目前y目标值
@param path ：移動的路徑

private static void explore(int targetX, int targetY, int currX, int currY, String path) {

if (currX == targetX && currY == targetY) {
    System.out.println("找到解：" + path);
} else if (currX <= targetX && currY <= targetY) {
    explore(targetX, targetY, currX, currY + 1, path + " N");
    explore(targetX, targetY, currX + 1, currY, path + " E");
    explore(targetX, targetY, currX + 1, currY + 1, path + " NE");
}

找到解：path: N N E

找到解：path: N E N

找到解：path: N NE

找到解：path: E N N

找到解：path: NE N

下圖則是上述搜尋對應的決策樹，其中五個深色的部分就是找到的解。

這種傳回到上一次選擇并繼續搜尋其他可能性的特性，是講該類方法成為回溯法的原因。找到解或者死路的時候，就傳回上一次進行選擇的情況，并嘗試其他可能，直到嘗試完所有可能的選擇。

參考文章：

來源：

https://muycode.cn/article/backtracking200409.html

《Java程式設計教程第三版》

原文位址

https://www.cnblogs.com/muycode/p/12671176.html

Java 中的遞歸

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希