[Program] 三分鐘連猴子都能理解的遞迴核心

不論您是否有寫過程式，本文目的就是讓任何人都可以在三分鐘理解遞迴的核心。

遞迴是程式中很常使用的到，但對於初學者來說確實有一點門檻，本篇就以[反向重組字串]範例說明。

目標: 反向重組字串，假設我有一個字串為"ＡＢＣＤ"，我要反向重組字串為"ＤＣＢＡ"。

這個看似很容易，但是如果有10000個字呢? 這時候就可用使用程式的遞迴來完成了。

反向重組字串，我們從人類的角度看，就是:
『把最後一個字記錄下來，並且把那個字移除，並組合起來』
然後不斷重複這個邏輯對吧，這就是遞迴！
而程式中就會把這個邏輯定義成一個方法 function
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
遞迴我認為可以拆解成兩個字，對照本範例如下:
＊把最後一個字記錄下來，並且把那個字移除 => 「遞」
＊資料組合起來 => 「迴」
＊要執行「迴」的步驟時，須要觸發判斷條件，也就是終止「遞」的步驟，否則就是無窮迴圈!!
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

而把這個過程轉成一個固定邏輯，重複使用該邏輯就是遞迴的核心！！！

遞迴的核心就是 "自己" 呼叫 "自己" ！
也因為自已呼叫自己，會有一層一層往內傳、多層嵌套的概念，就向俄羅斯娃娃一樣~

那先用一張圖，快速理解 反向重組字串 的過程。

後面用文字說明主邏輯:

1. 第一次呼叫方法，傳入'ABCD'，紀錄最後一碼'D'，並移除'D'，將'ABC'往下傳。
2. 第二次呼叫方法，傳入'ABC'，紀錄最後一碼'C'，並移除'C'，將'AB'往下傳。
3. 第三次呼叫方法，傳入'AB'，紀錄最後一碼'B'，並移除'B'，將'A'往下傳。
4. 第四次呼叫方法，傳入'A'，紀錄最後一碼'A'，並移除'A'，將''往下傳。
5. 第五次呼叫方法，傳入''，紀錄空字串''，因空值觸發停止條件，開始由後往前組合。
6. 回到第四次方法，拿到紀錄值'Ａ' ＋ 第五次紀錄值'' = 'A'。
7. 回到第三次方法，拿到紀錄值'Ｂ' ＋ 第四+五次紀錄值'Ａ' = 'ＢＡ'。
8. 回到第二次方法，拿到紀錄值'Ｃ' ＋ 第三+四+五次紀錄值'ＢA' = 'ＣＢA'。
9. 回到第一次方法，拿到紀錄值'Ｄ' ＋ 第二+三+四+五次紀錄值'ＣＢA' = 'ＤＣＢA'。

總結: 
    1～4 最後一個字記錄下來，並且把那個字移除 => 「遞」。
    5　  觸發停止條件，開始由後往前組合 => 終止「遞」的步驟。
    6～9 組合過程 => 「迴」。

附上程式碼。jsfiddle傳送門。

// 透過反向重組字串
function reStrFn(text){
    var reStr = ''

  if(text[text.length-1]){
    reStr += reStr + text[text.length-1]

    text = text.substring(0, text.length-1)

    reStr += reStrFn(text);
  }

    return reStr
}

console.log(reStrFn('ABCD'));

以下是關鍵核心:

1. 初始一定要宣告一個"總變數"，目的是要把每次遞迴的資料進行合併整理。(reStr)
2. 一定要設定"觸發遞迴的條件"，否則就會無窮迴圈。(if(text[text.length-1] )
3. 一定要接到，並且合併整理遞迴回傳的值，這就是遞迴的目的。(reStr += reStrFn(text))
4. 一定要回傳"總變數"，因為每一次遞迴都是獨立執行一次方法。(return reStr)
5. 整個過程就像是JS的冒泡事件，一層一層往下執行，再一層一層傳回來。

既然是自己呼叫自己，若是使用不當會造成無限迴圈，就是大家常說不建議使用遞迴或是效能差的原因。

但這些都不是理由，因為這就是一個工具而已，用的好就可以避免這些問題。

遞迴在初次學習時，是一個蠻抽象的概念，但多去思考一下，只要打通了，就會恍然大悟，原來是這樣！