內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

6.1遞歸應(yīng)用場景

看一個(gè)實(shí)際應(yīng)用場景，迷宮問題(回溯)，遞歸(recursion)

6.2遞歸的概念

簡單的說:遞歸就是方法自己調(diào)用自己,每次調(diào)用時(shí)傳入不同的變量.遞歸有助于編程者解決復(fù)雜的問題,同時(shí)可以讓代碼變得簡潔。

1.???? 打印問題

2.???? 階乘問題

3.???? 使用圖解的方式說明的遞歸的調(diào)用機(jī)制

4.???? 代碼演示

6.4遞歸能解決什么樣的問題

遞歸用于解決什么樣的問題

1.????? 各種數(shù)學(xué)問題如:8皇后問題﹐漢諾塔，階乘問題,迷宮問題,球和籃子的問題(google編程大賽)

2.????? 各種算法中也會(huì)使用到遞歸，比如快排，歸并排序，二分查找，分治算法等.

3.????? 將用棧解決的問題-->第歸代碼比較簡潔

6.5遞歸需要遵守的重要規(guī)則

1.????? 執(zhí)行一個(gè)方法時(shí)，就創(chuàng)建一個(gè)新的受保護(hù)的獨(dú)立空間(?？臻g)

2.????? 方法的局部變量是獨(dú)立的，不會(huì)相互影響,比如n變量

3.????? 如果方法中使用的是引用類型變量(比如數(shù)組)，就會(huì)共享該引用類型的數(shù)據(jù).

4.????? 遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸,出現(xiàn)StackOverflowError，死龜了:)

5.????? 當(dāng)一個(gè)方法執(zhí)行完畢，或者遇到return，就會(huì)返回，遵守誰調(diào)用，就將結(jié)果返回給誰，同時(shí)當(dāng)方法執(zhí)行完畢或者返回時(shí)，該方法也就執(zhí)行完畢

6.6遞歸-迷宮問題

6.6.1迷宮問題

6.6.2代碼實(shí)現(xiàn)

6.6.3對迷宮問題的討論

1.????? 小球得到的路徑，和程序員設(shè)置的找路策略有關(guān)即:找路的上下左右的順序相關(guān)

2.????? 在得到小球路徑時(shí)，可以先使用(下右上左)，再改成(上右下左)，看看路徑是不是有變化

3.????? 測試回溯現(xiàn)象

4.????? 思考:如何求出最短路徑?思路->代碼實(shí)現(xiàn)

思路：設(shè)計(jì)一個(gè)數(shù)組用數(shù)組表示不同的策略用for把策略走一遍，將每一個(gè)節(jié)點(diǎn)的2保存到一個(gè)集合中，看哪個(gè)集合的大小是最小的