前三天的練習我們深入「遞迴（Recursion）」的方法做了一連串的實作練習，不管是在鏈結串列或是樹結構，還有其他的問題中也都能看到遞迴的方法。所以遞迴絕對是你必須掌握的一種重要算法，能夠讓你的程式寫的更精簡、更優雅。我們一起回顧這幾個有趣的遞迴應用題：
這是一個鏈結串列中的「交換」的問題，實現「兩兩節點的數值交換」但「兩兩節點的鏈結不變」的題目。方法 ① 是很直覺利用迭代兩兩交換，每次記錄兩個節點數值交換，之後再將兩個節點指標往後移動；方法 ② 利用遞迴以兩個點為一組進行交換，在持續下一組直到全部交換完。
從二元樹中尋找兩個節點的共同上層（Lowest Common Ancestor（最低共同祖先））。第一種解法直接將此轉換成遞迴的形式，需要找的是「兩棵左右子樹的根節點」或「這兩個節點中最低的那個節點作為最低共同祖先（LCS）」。方法 ② 用迴圈的方式進行迭代，採用中序遍歷的方式將經歷過的點暫存到一個 Stack 中再一層一層回傳找到最近的上層；方法 ③ 第三種方法是我們可以分成兩個迴圈，第一個先找出其中一點的所有祖先，然後第二個迴圈去判斷是否有跟第一個點收集到的祖先重複。
這是一道類似「排列組合」的練習題。排列組合的基本想法就是把所有的可能窮舉出來，重點在於如何讓這個過程窮舉的過程更有效率。所以在本題裡面我們試著用遞迴的概念來轉化原本的問題，試著讓過程可以被簡化。方法 ① 採用窮舉法的方法用兩個迴圈把所有可能都跑過一次，只是在過程中會將「已經被考慮過元素組合剔除」。方法 ② 的遞迴法利用排列組合的概念，使用遞迴的方式來處理，從一個元素開始，每一層多增加一個元素的方式直到全部考慮完畢。
根據維基百科的定義：遞迴在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。程式語言支援函式的自呼叫，函式可以通過呼叫自身來進行遞迴 。一個遞迴函式的設計模式如下：
function foo(parameters) {
if (Base Case)
return 結果
else
General Case ( foo() )
}
Reference: GeeksforGeeks
遞迴執行時需要將「當前函式執行的狀況暫存下來，先中斷執行下一層」，具體可以分成以下幾個步驟：
Reference: tutorialspoint
根據維基百科的定義：回溯法是暴力搜尋法中的一種。 對於某些計算問題而言，回溯法是一種可以找出所有解的一般性演算法，尤其適用於約束補償問題。回溯法採用試錯的思想，它嘗試分步的去解決一個問題。
簡單來說，回溯其實就是在遞迴遞增地建立所有可能中，篩選掉不可能的組合，最終得到所要的答案。實務上我們也可以搭配深度優先先搜尋法 (DFS) 對每一個節點進行檢查，搭配遞迴或 Stack 計算過程中的暫存資料。
可以從「排列組合」的例子來看回溯跟真正的暴力法的差別，回溯法即是在暴力法窮舉的過程中，只考慮「真的」有可能出現的組合（如下圖）。
function recPermute(soFar, rest){
if(!rest) return soFar; //印出結果, 並回溯
for(var i = 0; i < rest.length; i++) { // 由所有可選擇中依序取一
var next = soFar + rest.charAt(i); // 由可選擇取一,與目前所選擇組合(串接)
var remaining = rest.substr(0,i) + rest.substr(i+1); // 移去已取出的 rest[i]
recPermute(next, remaining); // 由剩餘的來取出下個位置的字元(遞迴建立所有可能的組合)
}
}
function listPermutation(listString){
recPermute("", listString);
}
listPermutation("ABC");
嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。
iThome鐵人賽
看影片追技術