Iteration & Recursion 疊代遞迴

簡單來說，疊代法(iterative method)是用迴圈去循環重複程式碼的某些部分來得到答案，而遞迴法(recursive method)則是重複呼叫自身程式碼來得到答案。(參1)

一個可以同時使用疊代和遞迴來解釋的簡單例子:

求階乘　n! = 1 * 2 * 3 …*n

疊代法:是把已求得的數值，不斷重覆代入，再求得新數值的方法。

    0! = 1
    1! = 0!*1=1
    2! = 1!*2 = 2
    3! = 2!*3 = 6
    …
    n! = (n-1)! * n        (紅色部份為已知)

JavaScript:

function factorial(n)
{
    var answer = 1; //0!

    for(var loop=1; loop<=n; loop++) {
        answer = answer * loop; //(n-1)! * n
    }
    return answer;
}

var result = factorial(4);
document.write(result);

程式可於 jsBin online 執行.

遞迴法: 找出問題的規律，以此規律重複用相同手法來縮減問題範圍，直到能釐清細節，找到確定的部份。

    遞迴的種類:

        直接遞迴(Direct Recursion): 函式(Function)直接呼叫本身時稱之直接遞迴。

        間接遞迴(Indirect Recursion):函式呼叫另外的函式，再從另外函式呼叫原來的函式稱之間接遞迴。

    階乘的數學定義式(遞迴式):

其中規律的部份是 f(n) = n * f(n-1)，f(n) 會呼叫自己 f(n-1)，而 f(0) = 1 為確定的部份，也是遞迴的終止條件。

JavaScript:

function factorial(n)
{
if (n == 0) return 1; //終止條件
else return n * factorial(n - 1);
}

var result = factorial(4);
document.write(result);

程式可於 jsBin online 執行.

以 4! 為例，遞迴的執行過程：

factorial(4) = 4 * factorial(3)                         // 重複呼叫自己
                    = 4 * 3 * factorial(2)
                      = 4 * 3 * 2 * factorial(1)
                = 4 * 3 * 2 * 1 * factorial(0)
                      = 4 * 3 * 2 * 1 * 1                       //終止呼叫, 傳回 1
                = 4 * 3 * 2 * 1                             //傳回 2
                      = 4 * 3 * 2                                   //傳回 6
                = 4 * 6                                        //傳回 24
                      = 24

       一般人們較習慣用疊代的方式，因為是由已知的部分循序漸進推演，來得到答案。
       遞迴方法常用於解決無法找到初始的已知部分，而是找出一套縮小問題範疇的規律，
       以此規律不斷縮小問題，直到找到確定的部份。(參2)

      而其中最經典的例子就是河內之塔(Tower of Hanoi):

河內之塔是根據一個傳說形成的一個問題：

有三根杆子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則將所有圓盤移至C桿：

1.每次只能移動一個圓盤；

2.大盤不能疊在小盤上面。

提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規則。(參3)

若不了解此問題, 可以試玩一下河內之塔的遊戲:(參4)

以4個圓盤為例：

    思考方式:

        第一步圓盤1要移到B還是C呢?解決遞迴問題,通常初始動作不易找到,
        此時需由外往內(大到小)思考,想成要移動最大圓盤由A到C,要如何處理圓盤呢?

     圓盤移動方式:

        (1)為了完成圓盤1-4由A移到C, 必需將圓盤1-3由A移到B, 才能移動圓盤4由A移到C.

        (2)為了完成圓盤1-3由A移到B, 必需將圓盤1-2由A移到C, 才能移動圓盤3由A移到B.

        (3)為了完成圓盤1-2由A移到C, 必需將圓盤1 由A移到B, 才能移動圓盤2由A移到C.

完整移動步驟:


第一步由上面說明知道要將圓盤1移到B	既然圓盤1移到B,那圓盤2只能移到C

將圓盤1由B移到C,完成圓盤1-2由A移到 C	移圓盤3到B,再來將圓盤1-2由C移回B

要將圓盤1-2由C移到B,要先將圓盤1由Ｃ移到A	圓盤1移走後就可將圓盤2由Ｃ移到B了

將圓盤1由Ａ移到B,完成圓盤 1-3由A移到 B	現在可以將最大圓盤4由Ａ移到 C了,再來就是將圓盤1-3移由B移到C

要將圓盤1-3由B移到C,要先將圓盤1-2 由B移到A, 而要將圓盤2由B移到A,就要將圓盤1由B移到C	目的:要將圓盤3由B移到C, 圓盤1已由B移到C,再來就是把圓盤2移到A

將圓盤1由C移到A, 完成圓盤1-2由B移到A	把圓盤3由B移到C, 完成圓盤3,4移到Ｃ

要將圓盤1-2由A移到C,要先將圓盤1移到 B	圓盤２由A移到C, 完成圓盤,2,3,4移到C

最後將圓盤1移到C	完成

遞迴解說:

由上面的例子可以發現要移動N個圓盤由A桿移到C桿, 其步驟為:

(1) 將1 ~ N-1個圓盤由來源桿A 移到暫放桿B

(2) 將第N個圓盤移到目的桿C

(3) 再將1~ N-1個圓盤由暫放桿B, 移到目的桿C (完成)
而每次移動第N-1個圓盤到目的桿就要先將 1 ~ N-2 個圓盤全部移到暫放桿如此遞迴反覆直到只剩一個圓盤

JavaScript:

程式可於 jsBin online執行.

參考資料:

        (1) Iteration & Recursion: http://www.advanced-ict.info/programming/recursion.html
        (2) 演算法筆記: http://www.csie.ntnu.edu.tw/~u91029/IterativeRecursive.html
        (3) 河內之塔wiki: http://zh.wikipedia.org /wiki/河內塔
        (4) Tower of Hanoi DHTML game: http://www.dynamicdrive.com/dynamicindex12/hanoi.htm
        (5) 遞迴wiki: http://zh.wikipedia.org /wiki/遞迴

如有版權問題，請告知。