Recursive

http://www.programmer-club.com/pc2020v5/Forum/ShowSameTitleN.asp?URL=N&board_pc2020=general&id=2830
作者 : chiuinan2(青衫)

(1) recursive algorithm：

Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
    if n<=0 then 
        print("error")
    else if n=1 then 
        print(A,"→",B)
    else
       [ call HANOI(A,C,B,n-1); 
         print(A,"→",B);
         call HANOI(C,B,A,n-1) ]
end

設計的主要觀念為：
    1.將A柱中前n-1個環搬到C柱中暫置。（呼叫自己）
    2.將A柱中剩下最大的環搬到B柱中。
    3.將C柱中的n-1個環搬到B柱中。（呼叫自己）

(2)將recursive改成non-recursive的做法有很多種。如果已經知道recursive algorithm的話，最正統的方法便是直接將它化成non-recursive的形式。由recursive algorithm化成non-recursive algorithm的方法如下:

  1.在程式開頭處標上一個label。
  2.在每個呼叫自己的敘述的下一個敘述前，各標上一個label。
  3.把每個呼叫自己的敘述代換成一個將目前狀態push到stack的敘述，以及將程式參數改變的敘述，然後跳回程式的開頭。
  4.將每個返回敘述變成檢查stack的敘述，只有在stack為空時才能返回，否則必須pop出以前的狀態，然後跳到應返回的位置繼續執行。

上述的方法其實是在模擬程序遞迴呼叫的方式，label的記錄則是要得知其返回位址。因此本題的non-recursive algorithm便可以化成:

Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
step 1: 
    if n<=0 then 
        print("error")
    else if n=1 then 
        print(A,"→",B)
    else
        [ push(A,B,C,n-1,2);
          (A,B,C,n)←(A,C,B,n-1);
          goto step 1;
step 2:
          print(A,"→",B);
          push(A,B,C,n-1,3);
          (A,B,C,n)←(C,B,A,n-1);
          goto step 1; ]
step 3: 
    if stack not empty then
        [ pop(A,B,C,n,ret_step);
          goto ret_step ]
end

這個方法所得出的algorithm雖然不是最佳的，但是卻保證一定正確。當然您也可以利用程式技巧將它化簡成沒有label的結構化程式。另外一種方式是要靠靈感的，可說是可遇而不可求。例如上述algorithm，其實可以寫成:

Procedure HANOI（A,B,C,n) // 將n個環從A移到B //
step 1:
    if n<=0 then
        print("error")
    else if n=1 then
        print(A,"→",B)
    else
        [ Push(C,B,A,n-1);
          Push(A,B,C,1);
          Push(A,C,B,n-1) ]
    if stack not empty then
        [ pop（A,B,C,n);
          goto step 1 ]
end

使用三個push敘述來模擬三次搬運，相當簡潔。這是從觀察它的呼叫方式和stack的關係所發覺的，並無規則可循。雖然這個algorithm相當簡潔，但是執行速度並不是最好的。主要的原因是在於模擬recursice call的stack push和pop次數太多，因而減低了執行的速度。如果我們所要求的是速度的話，則必須儘量不要用stack的結構來模擬，應該從分析該問題non-recursive關係著手。這種過程一般都相當冗煩，而且不一定能夠做得到。這裡我們只列舉別人研究的成果供讀者參考，並做為以後您將來寫程式時的一個目標。Hanoi塔問題的non-recursive關係如下: