遞歸介紹

本來預算此章節是繼續寫快速排序的，然而編寫快速排序往往是遞歸來寫的，并且遞歸可能不是那么好理解，于是就有了這篇文章。

在上面提到了遞歸這么一個詞，遞歸在程序語言中簡單的理解是：方法自己調用自己

遞歸其實和循環是非常像的，循環都可以改寫成遞歸，遞歸未必能改寫成循環，這是一個充分不必要的條件。

那么，有了循環，為什么還要用遞歸呢？？在某些情況下(費波納切數列，漢諾塔)，使用遞歸會比循環簡單很多很多
話說多了也無益，讓我們來感受一下遞歸吧。

我們初學編程的時候肯定會做過類似的練習：

1+2+3+4+....+100(n)求和
給出一個數組，求該數組內部的最大值

我們要記住的是，想要用遞歸必須知道兩個條件：

遞歸出口(終止遞歸的條件)
遞歸表達式(規律)

技巧：在遞歸中常常是將問題切割成兩個部分(1和整體的思想)，這能夠讓我們快速找到遞歸表達式(規律)

一、求和

如果我們使用for循環來進行求和1+2+3+4+....+100，那是很簡單的：

int sum = 0;for (int i = 1; i <= 100; i++) {sum = sum + i;}System.out.println("公眾號：Java3y：" + sum);

前面我說了，for循環都可以使用遞歸來進行改寫，而使用遞歸必須要知道兩個條件：1、遞歸出口，2、遞歸表達式(規律)

首先，我們來找出它的規律：1+2+3+...+n，這是一個求和的運算，那么我們可以假設X=1+2+3+...+n，可以將1+2+3+...+(n-1)看成是一個整體。而這個整體做的事又和我們的**初始目的(求和)**相同。以我們的高中數學知識我們又可以將上面的式子看成X=sum(n-1)+n

好了，我們找到我們的遞歸表達式(規律)，它就是sum(n-1)+n,那遞歸出口呢，這個題目的遞歸出口就有很多了，我列舉一下：

如果n=1時，那么就返回1
如果n=2時，那么就返回3(1+2)
如果n=3時，那么就返回6(1+2+3)

當然了，我肯定是使用一個最簡單的遞歸出口了：if(n=1) return 1

遞歸表達式和遞歸出口我們都找到了，下面就代碼演示：

遞歸出口為1：

public static void main(String[] args) {System.out.println("公眾號：Java3y：" + sum(100));}/**** @param n 要加到的數字，比如題目的100* @return*/public static int sum(int n) {if (n == 1) {return 1;} else {return sum(n - 1) + n;}}

遞歸出口為4：

public static void main(String[] args) {System.out.println("公眾號：Java3y：" + sum(100));}/**** @param n 要加到的數字，比如題目的100* @return*/public static int sum(int n) {//如果遞歸出口為4，(1+2+3+4)if (n == 4) {return 10;} else {return sum(n - 1) + n;}}

結果都是一樣的。

二、數組內部的最大值

如果使用的是循環，那么我們通常這樣實現：

int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};//將數組的第一個假設是最大值int max = arrays[0];for (int i = 1; i < arrays.length; i++) {if (arrays[i] > max) {max = arrays[i];}}System.out.println("公眾號：Java3y：" + max);

那如果我們用遞歸的話，那怎么用弄呢？首先還是先要找到遞歸表達式(規律)和遞歸出口

我們又可以運用1和整體的思想來找到規律
- 將數組第一個數->2與數組后面的數->{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}進行切割，將數組后面的數看成是一個整體X={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}，那么我們就可以看成是第一個數和一個整體進行比較if(2>X) return 2 else(2<X) return X
- 而我們要做的就是找出這個整體的最大值與2進行比較。找出整體的最大值又是和我們的**初始目的(找出最大值)**是一樣的
- 也就可以寫成if( 2>findMax() )return 2 else return findMax()
遞歸出口，如果數組只有1個元素時，那么這個數組最大值就是它了。

使用到數組的時候，我們通常為數組設定左邊界和右邊界，這樣比較好地進行切割

L表示左邊界，往往表示的是數組第一個元素，也就會賦值為0(角標為0是數組的第一個元素)
R表示右邊界，往往表示的是數組的長度，也就會賦值為arrays.length-1（長度-1在角標中才是代表最后一個元素)

那么可以看看我們遞歸的寫法了：

public static void main(String[] args) {int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};System.out.println("公眾號：Java3y：" + findMax(arrays, 0, arrays.length - 1));}/*** 遞歸，找出數組最大的值* @param arrays 數組* @param L      左邊界，第一個數* @param R      右邊界，數組的長度* @return*/public static int findMax(int[] arrays, int L, int R) {//如果該數組只有一個數，那么最大的就是該數組第一個值了if (L == R) {return arrays[L];} else {int a = arrays[L];int b = findMax(arrays, L + 1, R);//找出整體的最大值if (a > b) {return a;} else {return b;}}}

三、冒泡排序遞歸寫法

在冒泡排序章節中給出了C語言的遞歸實現冒泡排序，那么現在我們已經使用遞歸的基本思路了，我們使用Java來重寫一下看看：

冒泡排序：倆倆交換，在第一趟排序中能夠將最大值排到最后面，外層循環控制排序趟數，內層循環控制比較次數

以遞歸的思想來進行改造：

當第一趟排序后，我們可以將數組最后一位(R)和數組前面的數(L,R-1)進行切割，數組前面的數(L,R-1)看成是一個整體，這個整體又是和我們的**初始目的(找出最大值，與當前趟數的末尾處交換)**是一樣的
遞歸出口：當只有一個元素時，即不用比較了：L==R

public static void main(String[] args) {int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};bubbleSort(arrays, 0, arrays.length - 1);System.out.println("公眾號：Java3y：" + arrays);}public static void bubbleSort(int[] arrays, int L, int R) {int temp;//如果只有一個元素了，那什么都不用干if (L == R) ;else {for (int i = L; i < R; i++) {if (arrays[i] > arrays[i + 1]) {temp = arrays[i];arrays[i] = arrays[i + 1];arrays[i + 1] = temp;}}//第一趟排序后已經將最大值放到數組最后面了//接下來是排序"整體"的數據了bubbleSort(arrays, L, R - 1);}}

四、斐波那契數列

接觸過C語言的同學很可能就知道什么是費波納切數列了，因為往往做練習題的時候它就會出現，它也是遞歸的典型應用。

菲波那切數列長這個樣子：{1 1 2 3 5 8 13 21 34 55..... n }

數學好的同學可能很容易就找到規律了：前兩項之和等于第三項

例如：

 	1 + 1 = 22 + 3 = 513 + 21 = 34

如果讓我們求出第n項是多少，那么我們就可以很簡單寫出對應的遞歸表達式了：Z = (n-2) + (n-1)

遞歸出口在本題目是需要有兩個的，因為它是前兩項加起來才得出第三項的值

同樣地，那么我們的遞歸出口可以寫成這樣：if(n==1) retrun 1 if(n==2) return 2

下面就來看一下完整的代碼吧：

public static void main(String[] args) {int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};//bubbleSort(arrays, 0, arrays.length - 1);int fibonacci = fibonacci(10);System.out.println("公眾號：Java3y：" + fibonacci);}public static int fibonacci(int n) {if (n == 1) {return 1;} else if (n == 2) {return 1;} else {return (fibonacci(n - 1) + fibonacci(n - 2));}}

五、漢諾塔算法

圖片來源百度百科：

玩漢諾塔的規則很簡單：

有三根柱子，原始裝滿大小不一的盤子的柱子我們稱為A，還有兩根空的柱子，我們分別稱為B和C(任選)
最終的目的就是將A柱子的盤子全部移到C柱子中
- 移動的時候有個規則：一次只能移動一個盤子，小的盤子不能在大的盤子上面(反過來：大的盤子不能在小的盤子上面)

我們下面就來玩一下：

只有一個盤子：
- 將A柱子的盤子直接移動到C柱子中
- 完成游戲
只有兩個盤子：
- 將A柱子上的小盤子移動到B柱子中
- 將A柱子上的大盤子移動到C柱子中
- 最后將在B柱子的小盤子移動到C柱子大盤子中
- 完成游戲
只有三個盤子：
- 將A柱子小的盤子移動到C柱子中
- 將A柱子上的中盤子移動到B柱子中
- 將C柱子小盤子移動到B柱子中盤子中
- 將A柱子的大盤子移動到C柱子中
- 將B柱子的小盤子移動到A柱子中
- 將B柱子的中盤子移動到C柱子中
- 最后將A柱子的小盤子移動到C柱子中
- 完成游戲

.......................

從前三次玩法中我們就可以發現的規律：

想要將最大的盤子移動到C柱子，就必須將其余的盤子移到B柱子處(借助B柱子將最大盤子移動到C柱子中[除了最大盤子，將所有盤子移動到B柱子中])[遞歸表達式]
當C柱子有了最大盤子時，所有的盤子在B柱子。現在的目的就是借助A柱子將B柱子的盤子都放到C柱子中(和上面是一樣的，已經發生遞歸了)
當只有一個盤子時，就可以直接移動到C柱子了(遞歸出口)
- A柱子稱之為起始柱子，B柱子稱之為中轉柱子，C柱子稱之為目標柱子
- 從上面的描述我們可以發現，起始柱子、中轉柱子它們的角色是會變的（A柱子開始是起始柱子，第二輪后就變成了中轉柱子了。B柱子開始是目標柱子，第二輪后就變成了起始柱子。總之，起始柱子、中轉柱子的角色是不停切換的)

簡單來說就分成三步：

把 n-1 號盤子移動到中轉柱子
把最大盤子從起點移到目標柱子
把中轉柱子的n-1號盤子也移到目標柱子

那么就可以寫代碼測試一下了(回看上面玩的過程)：

public static void main(String[] args) {int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};//bubbleSort(arrays, 0, arrays.length - 1);//int fibonacci = fibonacci(10);hanoi(3, 'A', 'B', 'C');System.out.println("公眾號：Java3y" );}/*** 漢諾塔* @param n n個盤子* @param start 起始柱子* @param transfer 中轉柱子* @param target 目標柱子*/public static void hanoi(int n, char start, char transfer, char target) {//只有一個盤子，直接搬到目標柱子if (n == 1) {System.out.println(start + "---->" + target);} else {//起始柱子借助目標柱子將盤子都移動到中轉柱子中(除了最大的盤子)hanoi(n - 1, start, target, transfer);System.out.println(start + "---->" + target);//中轉柱子借助起始柱子將盤子都移動到目標柱子中hanoi(n - 1, transfer, start, target);}}

我們來測試一下看寫得對不對：