tail recursion 真的比較好嗎

在沒有 Tail-recursion 得程式中

5!是這樣算的

F(5)*F(4)

F(5)*F(4)*F(3)

F(5)*F(4)*F(3)*F(2)

F(5)*F(4)*F(3)*F(2)*F(1)

F(5)*F(4)*F(3)*F(2)*1

F(5)*F(4)*F(3)*2

F(5)*F(4)*6

F(5)*24

120

最後回傳乘結果

那在Tail-recursion中

5!是這樣算的

5*F(4)

20*F(3)

60*F(2)

120*F(1)

120

回傳120

我覺得不是這樣...

因為20*F(3) 很奇怪阿

實作真的是這樣嗎?

我的想法還是覺得他會先去呼叫F(4)

而不會把20先算出來吧是回傳在算才對吧?

所以我覺得兩個的使用空間不是一樣多嗎?

4 Answers

Rating
  • 1 decade ago
    Favorite Answer

    int facT(int n, int t) // Tailing

    { if (n) return facT(n-1, t*n);

    else return t;

    }

    int facA(int n) // Augmenting

    { if (n) return n * facA(n-1);

    else return 1;

    }

    int main()

    { int i;

    for (i=0; i<13; i++)

    printf("%2d! =%10d%10d\n", i, facA(i), facT(i, 1));

    system("pause");

    return 0;

    }

    Tailing Recursion (TR) 真是麻煩!經常還要多一個參數!怎麼會快!?

    圖片參考:http://tw.yimg.com/i/tw/ugc/rte/smiley_6.gif

    有時還會要多遞迴一次!怎麼會快!?

    圖片參考:http://tw.yimg.com/i/tw/ugc/rte/smiley_25.gif

    明明經常要多一個參數,就是要多一個空間,怎會省空間!?

    圖片參考:http://tw.yimg.com/i/tw/ugc/rte/smiley_12.gif

    事實不是如此!

    圖片參考:http://tw.yimg.com/i/tw/ugc/rte/smiley_11.gif

    只要是呼叫一個函數後,〝直接〞傳回函數值的,

    好的compiler,都可以把它加速,這叫Taile Call Optimization (TCO)!

    如:return sin(x+y);

    但:return sin(x) + sin(y); 就不是!

    TCO優化包括時間與空間。

    (我覺得優化比最佳化比較接近正確的意思,不是親中國!)

    它是在Activation Record (AR) 上動了手腳!

    (AR是Compiler重要的〝基本〞東西,

     對非CS、不研究Compiler的人而言,可以略過不理。)

    〝簡〞言之,它通常可以變成 goto(如:Perl),因此就少了:

     1. 一個return。

      (return是一種pop,要能pop要先push!所以,省了一堆!)

     2. 一個AR所需的空間!(有時不行)

    雖然TCO優化包括時間與空間。但其時空的優化量都很有限!

    不過,一但做到遞迴裡,那就大有不同!

    1. 一定可以變成goto!

    2. 一定可以省一個AR!(省法因Compiler不同而不同!)

    因此,在多層的遞迴下,TR真的會快!

    且不吃寶貴、有限的stack空間!

    前提:Compiler有支援TCO!

    也就是說:在Compiler不支援TCO的情況下,TR反而會變慢、有時也浪費空間!

    至於怎麼實做,我已Post一個C版的階乘在最上面,你Trace一下就會知道了。

    想學好TR,要去學Functional Language。

    2008-11-21 07:03:11 補充:

    難得和老師意見相左!(最後半句話:但這種設計...)

    Tail Recursion (TR) 在 Functional Language (FL) 上是大量使用!

    也因此剌激了Tail Call Optimization (TCO) 的研究與發展。

    而 FL近年發展速度,

    在設計形態上,已能與OO相爭為解決大程式設計的方法!

    在平行程式上,一些學者已懷疑FL為平行程式的解決之道!

    2008-11-21 07:03:22 補充:

    FL思考路線與大家常用的 IL(如:C, Fortran, MatLab, BASIC, ASM等)不同!

    不少人學不起來(個人就是! T.T)

    學得起來的,已寫出不少與C可以拚速度的程式!

    程式短小,重用性高!

    所以,它是不好學,不是不方便!

    (應該說是:比 IL 更選人學吧!)

    2008-11-25 20:15:23 補充:

    參這篇的意見

    http://tw.knowledge.yahoo.com/question/question?qi...

    • Login to reply the answers
  • litfal
    Lv 5
    1 decade ago

    好多專有名詞...

    感覺用VB都不會遇到這些問題

    沒關係! 維基百科陪我過夜!(好樣的tail recursion只有英文版...)

    以實例來理解的話

    tail recursion可適用在[重頭做到尾]或[重尾做到頭]都一樣的遞迴上?

    例如連加或連乘?

    而且把到自己的結果傳給了下一個堆疊?

    費氏數列好像可以符合這種類型,試著寫了一下:

    2008-11-24 05:33:28 補充:

    long fib_A(int n){ // Augmenting

    if (n==1) return 1;

    else if(n) return fib_A(n-1)+fib_A(n-2);

    else return 0;

    }

    long fib_T(int n,long t1,long t2){ // Tailing

    if (n) return fib_T(n-1,t2,t1+t2);

    return t1+t2;

    }

    2008-11-24 05:35:08 補充:

    int main(){

    printf("%d\n",fib_A(45));

    printf("%d\n",fib_T(45-2,0,1));

    system("pause");

    return 0;

    }

    這樣效率的確是差很多...

    但是好像又怪怪的, fib_A和fib_T長得不太像

    不像階層的題目A與T的函數幾乎一樣

    2008-11-24 17:29:16 補充:

    還有就是常常在討論遞迴, 但很多題目其實用迴圈就能做了

    例如例子的階層, 和費氏數列

    long fib_loop(int n){

     long t1,t2,tmp;

     if (n){

      for(n=n-1,t1=0,t2=1;n;n--)

       {tmp=t2;t2+=t1;t1=tmp;}

      return t2;}

     else return 0;

    }

    同樣能達成目的,到底實作上哪樣的效率比較好?

    • Login to reply the answers
  • SiYu
    Lv 5
    1 decade ago

    Lisp function language 真的不好寫. 我只有修過程式語言的課才寫過. 現在要我碰. 逃跑比較快.

    • Login to reply the answers
  • Inunu
    Lv 5
    1 decade ago

    一個是:

    F(5) * ( F(4) * ( F(3) * ( F(2) * F(1) ) ) )

    另一個是:

    ( ( ( F(5) * F(4) ) * F(3) ) * F(2) ) * F(1)

    其實沒差別, 該來的總是要來.

    在資料的流向上, 前者的最後答案是在 F(5) 獲得, 後者則是在 F(1) 獲得. 設計語法上前者適合傳回答案, 因此在 F(5) 處理. 後者適合將目前的答案向下傳遞, 並在 F(1) 地方處理.

    只要 F(1) 能進行適當的處理, 可以省略回傳部份. 但這種設計在使用上較不方便.

    • Login to reply the answers
Still have questions? Get your answers by asking now.