再論遞歸

大概是從漢諾塔hanoi了解遞歸算法的：

function hanoi(n, a, b, c) {if(n===1) {console.log(`${a} ---> ${c}`)return}hanoi(n-1, a, c, b);hanoi(1, a, b, c);hanoi(n-1, b, a, c); }hanoi(10, 'A', 'B', 'C');

我自詡腦回路清奇，然而面對這層層遞歸，大腦CPU卻顯得不堪重負，甚至一度崩盤！并且作為一個~偽~編程人員，如果讓別人知道我對遞歸這樣的基本算法都搞不定，顏面何存吶？！！所以，對此我一直耿耿于懷。

直到昨天晚上（2017/12/21真是個偉大的日子），我在知乎看到一個回答，簡單粗暴。原答案見python中的漢諾塔遞歸算法的具體運算過程是怎樣的？

@半島 的回答：

重點其實是：不要一開始就關心每一步怎么解決的，你只需要把函數當成一個實現你目的的神器，隨時調用。也就是遞歸。

01

比如說我們有一個萬能神器move，只需要給它幾個參數，即可自動完成一個功能：把n個盤子利用緩沖區，從起點運送到終點，期間嚴格遵守漢諾塔規則。
這里你暫時不需要去了解每一個步是如何實現的。

move(N,起點，緩沖區，終點）
N: 盤子的個數。

02

現在有個n個盤子，a,b,c三個塔。
把n個盤子抽象成兩個盤子，n-1 和 底下最大的1:n = (n-1) + 1

這個最簡單的玩法如何實現呢？

• 首先：把n-1 移到 緩沖區 -------過程1
• 然后：把1 移到 終點 -------過程2
• 最后：把緩沖區的n-1 移到 終點 -------過程3

03

過程1 如何實現？
還是召喚神器吧。
move(N,起點，緩沖區，終點）
此時，我們的起點是a,終點是b ,N=n-1,緩沖區只能是c了
move(n-1,a,c,b)
過程2呢？
move(1,a,b,c)
過程3呢？
move(n-1,b,a,c)

04

哦哦 神器的力量太大，止不住咋辦。。

if (N == 1):
a -> c #此時我已經不需要緩沖區了

---

過程1-3是整個遞歸算法的核心。再抽象一點，即把大象裝進冰箱攏共需要三步：

• 打開冰箱門
• 把大象裝進冰箱
• 關上冰箱門

oh my my，勝利的號角已經吹響，五星紅旗在敵人的陣地上迎風招展！

實現遞歸的基本步驟

• 1、實現一個功能需要 n 次遞歸調用；
• 2、假設前面 n-1 次已經執行完畢；
• 3、執行最后一步操作
• 4、添加遞歸邊界條件

判別遞歸使用場景

最后，什么時候需要用到遞歸呢？一個簡單的判別方法是：當前的輸入依賴上一步的輸出，依次重復。

最后的最后，做一個小練習加深一下印象吧：

/* 小易準備去魔法王國采購魔法神器,購買魔法神器需要使用魔法幣,但是小易現在一枚魔法幣都沒有,但是小易有兩臺魔法機器可以通過投入x(x可以為0)個魔法幣產生更多的魔法幣。 魔法機器1:如果投入x個魔法幣,魔法機器會將其變為2x+1個魔法幣 魔法機器2:如果投入x個魔法幣,魔法機器會將其變為2x+2個魔法幣 小易采購魔法神器總共需要n個魔法幣,所以小易只能通過兩臺魔法機器產生恰好n個魔法幣,小易需要你幫他設計一個投入方案使他最后恰好擁有n個魔法幣。 輸入描述: 輸入包括一行,包括一個正整數n(1 ≤ n ≤ 10^9),表示小易需要的魔法幣數量。輸出描述: 輸出一個字符串,每個字符表示該次小易選取投入的魔法機器。其中只包含字符'1'和'2'。輸入例子1: >10輸出例子1: >12*/// TODO:// js實現// 最初實現思路 function createMagic(n) {let arr = [];function magicCoin(n) {// 遞歸邊界if (n < 1 || n > Math.pow(10,9)) return;if (n === 1) return arr.push(1);if (n === 2) return arr.push(2);if (n % 2 === 0) {magicCoin((n - 2) / 2);arr.push(2);} else {magicCoin((n - 1) / 2);arr.push(1);}}magicCoin(n);return arr.join('') }// 略微優化 function magicCoin(n) {if (n < 1) return;if (n % 2 === 0) {return magicCoin((n - 2) / 2) + '2';} else {return magicCoin((n - 1) / 2) + '1';} }// testfor(var i = 1; i<20; i++) {console.log(i+': ' +createMagic(i)); }// 輸出 1: 1 2: 2 3: 11 4: 12 5: 21 6: 22 7: 111 8: 112 9: 121 10: 122 11: 211 12: 212 13: 221 14: 222 15: 1111 16: 1112 17: 1121 18: 1122 19: 1211

敬請勘誤指正！

轉載于:https://www.cnblogs.com/fayin/p/8086790.html

總結

以上是生活随笔為你收集整理的再论递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。