摘要:那么,有了循環,為什么還要用遞歸呢在某些情況下費波納切數列,漢諾塔,使用遞歸會比循環簡單很多很多話說多了也無益,讓我們來感受一下遞歸吧。
遞歸介紹
本來預算此章節是繼續寫快速排序的,然而編寫快速排序往往是遞歸來寫的,并且遞歸可能不是那么好理解,于是就有了這篇文章。
在上面提到了遞歸這么一個詞,遞歸在程序語言中簡單的理解是:方法自己調用自己
遞歸其實和循環是非常像的,循環都可以改寫成遞歸,遞歸未必能改寫成循環,這是一個充分不必要的條件。
那么,有了循環,為什么還要用遞歸呢??在某些情況下(費波納切數列,漢諾塔),使用遞歸會比循環簡單很多很多
話說多了也無益,讓我們來感受一下遞歸吧。
我們初學編程的時候肯定會做過類似的練習:
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
而我們要做的就是找出這個整體的最大值與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 = 2 2 + 3 = 5 13 + 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); } }
我們來測試一下看寫得對不對:
參考資料:
https://www.zhihu.com/question/24385418
六、總結遞歸的確是一個比較難理解的東西,好幾次都把我繞進去了....
要使用遞歸首先要知道兩件事:
遞歸出口(終止遞歸的條件)
遞歸表達式(規律)
在遞歸中常常用”整體“的思想,在漢諾塔例子中也不例外:將最大盤的盤子看成1,上面的盤子看成一個整體。那么我們在演算的時候就很清晰了:將”整體“搬到B柱子,將最大的盤子搬到C柱子,最后將B柱子的盤子搬到C柱子中
因為我們人腦無法演算那么多的步驟,遞歸是用計算機來干的,只要我們找到了遞歸表達式和遞歸出口就要相信計算機能幫我們搞掂。
在編程語言中,遞歸的本質是方法自己調用自己,只是參數不一樣罷了。
最后,我們來看一下如果是5個盤子,要運多少次才能運完:
PS:如果有更好的理解方法,或者我理解錯的地方大家可以在評論下留言一起交流哦!
如果文章有錯的地方歡迎指正,大家互相交流。習慣在微信看技術文章,想要獲取更多的Java資源的同學,可以關注微信公眾號:Java3y
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68863.html
摘要:簡而言之,遞歸就是自己調用自己,但是這個調用它是有一定條件的,比如子問題須與原始問題為同樣的事,且更為簡單。當時,這層遞歸返回,也就是返回到的這層遞歸。這時,至此,遞歸結束,返回結果給調用方。 showImg(https://segmentfault.com/img/bVbvZRe?w=1242&h=735); 什么是遞歸? 維基百科給出了如下定義: 程序調用自身的編程技巧稱為遞歸.遞...
摘要:今天我們繼續使用的擼我們的實戰項目,只有在實戰中我們才會領悟更多,光紙上談兵然并卵,繼上篇我們的一個案例引發的動態組件與全局事件綁定總結之后,今天來聊一聊我們如何在項目中使用遞歸組件。 今天我們繼續使用 Vue 的擼我們的實戰項目,只有在實戰中我們才會領悟更多,光紙上談兵然并卵,繼上篇我們的《Vue一個案例引發的動態組件與全局事件綁定總結》 之后,今天來聊一聊我們如何在項目中使用遞歸組...
摘要:如果存在這么個函數,那么我們就可以通過求解的不動點來求出了。尋找轉換函數的不動點找到了轉換函數后,下一步就是確定其不動點了,而這個不動點就是我們最終想要的。 本文原發于個人博客 遞歸 作為計算機科學中很重要的一個概念,應用范圍非常廣泛。比較重要的數據結構,像樹、圖,本身就是遞歸定義的。比較常見的遞歸算法有階乘、斐波那契數等,它們都是在定義函數的同時又引用本身,對于初學者來說也比較好理解...
摘要:不斷執行這個操作代碼實現快速排序用遞歸比較好寫如果不太熟悉遞歸的同學可到遞歸就這么簡單。 前言 大概花了一周的時間把八大基礎排序過了一遍,這篇博文主要是用來回顧一下八大基礎排序的要點和一些總結~ 回顧: 冒泡排序就這么簡單 選擇排序就這么簡單 插入排序就這么簡單 快速排序就這么簡單 歸并排序就這么簡單 堆排序就這么簡單 希爾排序就這么簡單 基數排序就這么簡單 總的來說:快速排序是用...
閱讀 3384·2023-04-25 20:37
閱讀 3142·2021-09-07 09:59
閱讀 1665·2019-08-29 12:43
閱讀 1185·2019-08-28 18:27
閱讀 479·2019-08-26 13:50
閱讀 2025·2019-08-26 10:33
閱讀 3591·2019-08-23 18:39
閱讀 2390·2019-08-23 18:09