一文學會遞迴遞推
2022-01-06由 堆疊樹圖 發表于 林業
遞迴數列方程怎麼推導
遞迴演算法和遞推演算法無論是在ACM競賽還是專案工程上都有著極為廣泛的應用，但想要完全掌握兩者的思想並不容易，對於剛剛接觸程式設計的人來說更是這樣，我在初次接觸遞迴遞推時就吃了很多的苦頭，除了當時對程式語言不太熟悉之外，最大的原因就是難以理解其中的思想，本文將二者結合程式碼分別講解，力求以“理論+實踐”的方式使讀者明白兩種演算法。一箭雙鵰，一文雙遞。
一。遞迴和遞推的區別
學習遞迴遞推的一個容易遇到的問題就是混淆二者的概念。所以學習時首先就要明白二者的區別。
二者的區別也可以看做二者的概念。
遞迴：一個方法/函式的自我巢狀，從結果出發一直向前回溯到初始狀態（值），是一種程式自身呼叫自身的技巧，類似於套娃。舉個栗子。
從前有座山，山裡有座廟，廟裡有個老和尚，在給小和尚講故事。講的什麼故事呢？從前有座山，山裡有座廟，廟裡有個老和尚，在給小和尚講故事。講什麼故事呢？從前有座山，山裡有座廟，廟裡有個老和尚，在給小和尚講故事。講的什麼故事呢？從前有座山，山裡有座廟，廟裡有個老和尚，在給小和尚講故事
這個大家耳熟能詳的“老和尚講故事”就是典型的遞迴。
遞推：與遞迴的從結果找初始狀態（值）相反，遞推是已知初始狀態（值），一步步計算得到最後的結果。高中數學中的數列經常會使用遞推式。如：
S(n) = S(n - 1) + n ; D(n)=D(n-1)+D(n-2)+3
從上述樣例可以看出，一個數列的某一項是透過它的前一項或前幾項透過某種計算得到的。
二。遞迴–自我呼叫，遞盡而歸
1。遞迴條件
（1）原問題可以變成更簡單，規模更小的子問題，且原問題和子問題相似。
（2）一定要存在遞迴出口，即遞迴的結束條件。比如設定某種情況，在這種情況下會使遞迴函式返回，做到遞盡而歸。否則函式會一直遞迴下去，造成死迴圈。
2。遞迴圖解
“一圖勝千言”，用圖解的方式可以更好的理解遞迴。
給出一個正整數n，計算出1+2+。。。+n的結果
這道題最快的方法是用求和公式，但是為了體現出遞迴的概念，這裡採用遞迴的思想。
import java。util。Scanner；public class ADD { public static void main（String［］ args） { Scanner scanner=new Scanner（System。in）； int n=scanner。nextInt（）； System。out。printf（“sum=%d\n”，sum（n））； } private static int sum（int n）{ if（n==1）return 1；//到1開始返回 return sum（n-1）+n；//否則繼續遞迴，當前值和遞迴返回值相加 }}
遞迴圖
從圖中可以看出，函式先是不斷的呼叫自身，函式每呼叫一次，引數就減一，當引數減到一的時候，函式開始返回1給上一層，就這樣一層層返回。
3。典型題的程式碼實現
既然是“理論+實踐”，那習題是必不可少的了。學習演算法需要刷題，學好演算法需要大量的習題作為支援。
遞迴乘法。 寫一個遞迴函式，不使用 * 運算子， 實現兩個正整數的相乘。可以使用加號、減號、位移，但要吝嗇一些。
思路：首先根據題幹要求，‘*’是無法使用的，且一定要用遞迴來完成，所以我們很容易想到用“加法+遞迴”的方式實現。
程式碼：
class Solution { public int multiply（int A， int B） { return add（A，B）； } public int add（int A，int B）{ if（A==0）return 0； if（A>B）return add（B，A）；//選擇較小的數來作為控制呼叫次數的引數，可以節省時間和避免棧溢位 return add（A-1，B）+B； }}
注：此題來自leetcode。連結：https：//leetcode-cn。com/problems/recursive-mulitply-lcci/
漢諾塔。 法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝納勒斯（在印度北部）的聖廟裡，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。
這個傳說是否真實我們不得而知，但是漢諾塔問題已經成為了學習遞迴時的一個再經典不過的問題了，在學習遞迴的過程中，十之八九都會遇到漢諾塔問題。
在經典漢諾塔問題中，有 3 根柱子及 N 個不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開始，所有盤子自上而下按升序依次套在第一根柱子上（即每一個盤子只能放在更大的盤子上面）。移動圓盤時受到以下限制：
（1） 每次只能移動一個盤子；
（2） 盤子只能從柱子頂端滑出移到下一根柱子；
（3） 盤子只能疊在比它大的盤子上。請編寫程式，用棧將所有盤子從第一根柱子移到最後一根柱子。
思路：我們把三根柱子分別命名為A，B，C，開始時所有盤子都疊在A柱子上，要透過若干步全部轉移到C上。假設N=1，則可以直接把盤子從A放到C上。當N=2時，就無法直接從A搬到C上了，這時B的作用就體現出來了。當N>1時，B就起到了一個“中轉站”的作用，盤子可以先放到B上寄存，等可以放到C上時再放。可以把N個盤子分成上面的N-1個和最底下的1個，先把上面的N-1個透過C放到B上，再把底下的1個放到C上，最後再把B上的N-1個透過A放到C上。說著容易，N-1個盤子怎麼移動呢，這就是遞迴的用武之地了，我們已經把N的問題變成N-1的問題了，所以可以進一步變成N-2的問題，這樣下去一直到1個盤子的問題
class Solution { public void hanota（List
注：此題來自leetcode。連結：https：//leetcode-cn。com/problems/hanota-lcci
三。遞推–初值傳遞，層層推進
1。一般方法
遞推常常是某種規律用公式的形式表達出來，因此該演算法一般都會先找出遞推式，然後由遞推式算出結果。
2。斐波那契數列
斐波那契數列是數學家萊昂納多·斐波那契在研究兔子繁殖時引入的，也稱為“兔子序列”。如下：
1 ， 1 ， 2 ， 3 ， 5 ， 8 ， 13 ， 21 ， 34 ， · · ·
這個序列解釋起來很簡單，序列前兩項為1，從第三項開始每一項都是前兩項之和。遞推式可以看成
Fib[n]=1,n=0||n=1
Fib[n]=Fib[n-1]+Fib[n-2],n>=3
現在我們知道了數列的初值（前兩項），也知道了遞推式，求關於斐波那契數列的問題就很容易了。
public class Fibonacci { public static void main（String［］ args） { int［］ Fib=new int［10］； Fib［0］=1； Fib［1］=1；； for（int i=2；i<9；i++）{ Fib［i］=Fib［i-1］+Fib［i-2］； } }}
3。典型題的程式碼實現
楊輝三角。楊輝三角是是二項式係數在三角形中的一種幾何排列，最初是被用來探究（a+b）［^n］的展開問題，在計算機中也是組合數學和遞推演算法的常用模型。
·
楊輝三角
透過上圖可以看出，楊輝三角中每行的最左邊和最右邊的數都是1，且第n行就會有n個數字，一個數字是上面的兩個數字之和。可求出的遞推表示式為
tri[i][j] = tri[i-1][j-1] + tri[i-1][j]
public class Triangle { public static void main（String［］ args） { int［］［］ tri=new int［33］［33］；//楊輝三角用陣列儲存 for（int i=0；i<=10；i++）{ tri［i］［0］=tri［i］［i］=1；//每行的最左邊和最右邊的數都是1，所以先把兩邊的數都設定成1 for（int j=1；j 輸出結果陣列中的值為0的項刪除後，得到的結果如下 11 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 伯努利-尤拉錯排問題。 問題的最初形式是錯裝信封的問題。假設有n個信封，n封信，每封信都有對應的信封。求每封信都被裝錯的可能有多少種。後來就慢慢演化為有n個元素，在某種方式的排列以後，每個元素都不在原來位置上的可能有多少種。 分析：設錯裝信封的可能數為D（n），首先拿出第n封信，按照規則可以放在除第n個信封之外的另外n-1個信封中，假設第n封信被放到了第k個信封中（k！=n），這時信和信封各減一，此時有兩種可能。 第k封信被放在了第n個信封中，這時信和信封又各減一，就有n-2個信封，n-2封信，可能數為D（n-2） 第k封信沒有被放在第n個信封中，就有n-1個信封，n-1封信，第k封信既然一定不會被放到第n個信封中，那麼第k封信就可以認為是第n封信，這樣就相當於只是把第k封信和第k個信封拿走，而其它的不變，可能數為D（n-1） 兩種可能相加就是一共的可能數，經分析得到遞推式 D(n) = (D(n-2) + D(n-1)) * (n-1) 因為信k和信封k是從n-1個信和n-1個信封中任意抽取的，所以要在最外面乘以n-1 程式碼： import java。util。Scanner；public class cuopai { public static void main（String［］ args） { Scanner scanner=new Scanner（System。in）； int n=scanner。nextInt（）； int［］ D=new int［n+1］； if（n==1）{ System。out。println（0）； }else if（n==2）{ System。out。println（1）； }else if（n>=3）{ D［1］=0； D［2］=1； for（int i=3；i<=n；i++）{ D［i］=（i-1）*（D［i-1］+D［i-2］）； } } System。out。println（D［n］）； }} 如果您覺得這篇文章對您有所幫助，歡迎關注我的微信公眾號–【懸浮流星】，閱讀更多的類似文章。如果您發現該文章有錯誤或不足之處，也歡迎批評指正。