遞迴與非遞迴的不同

Q: 遞迴->非遞迴，主要原理是什麼? 實作方法為何?


遞迴程式就是自己呼叫自己,相信這大家都知道,在乎叫的時候,一定要記錄下
返回位置,以便程式結束時可以原呼叫點 : 下列用費氏數列來舉例 :

Function Fib(n:integer):integer;
begin
if (n=0) or (n=1) then
result := n
else
result := Fib(n-1)+Fib(n-2)
end;

短短幾行解決了費氏數列, 在遞迴呼叫時, OS 幫你解決了返回位置,
及變數儲存的問題, 程式簡單明瞭,但是執行效率較差,對於講求速度的
FORTRAN 來講是不被允許的, 我記得是因為 static 變數的關係,
一般遞迴程式大都可以改成非遞迴 , 只要有幾種方式 :
1. 利用迴圈
2. 利用 Goto 指令 ,

向階乘可以用遞迴, 但我們也可以用迴圈 :
for i := 1 to n do
result := result * i

無法用迴圈的就要用 goto 指令了,但是複雜許多, 因為要自己處理
Stack(pop,push) 的動作.

如果您有興趣,可以去看看資料結構的書,像二元樹的前,中,後序走訪
河內塔等演算法都可用遞迴來實做,其中也會提及如何改成非遞迴.

優點 缺點(相較於非遞迴) Stack..
遞迴 : 程式簡單明瞭 執行效率較差 OS 幫 Program 處理
非 ..: 程式較複雜 執行效率較好 Program 要自己做

如果你是寫 AP, 沒有必要自己找麻煩,能交給 OS,就交給 OS 做.
當然,如果你是寫作業系統,就自己來嘍.......



> > 河內塔可以用遞迴的方式處理, 但不是每種語言都支援遞迴,例如 FORTRAN ,
> > 因為遞迴雖然讓程式簡單明瞭,但速度較慢,因為要處理 Stack 及一些返回位置等,
> > 還有 static 變數的問題....
> > (但是一般的遞迴大都可改成非遞迴)

0 Comments Tags： | edit post