Tail Recursion

想起當初面試時候有被問過寫遞迴的階乘，很自然的就寫成這樣：

int factorial(int n){
   if (n==1)
      return 1;
   else
      return n * factorial(n-1);
}

被問說有沒有更快的方法，當然是不知道。

後來在看Introduction to Algorithms裡面講quick sort的時候有看過這個名詞，但是會錯意了，最近看subject GRE又看到Tail Recursion這種東西，才知道是什麼意思。可能是當初問試官想要的解答？

Tail Recursion原本是從LISP等的函數語言跑過來的東西。在一般程序語言上就變成有寫特別的寫法，會讓compiler在最佳化的時候自動展開遞迴，速度就會變成和迴圈差不多。上面的改寫版本就是：

int factorial(int n){
   return fac(n, 1);
}

int fac( int n, int accumulate ){
   if (n==1)
      return accumulate;
   else
      return fac( n-1, n* accumulate);
}

特色就是回傳的地方，前面不會乘一個東西，還有多加了一個累積算到目前結果的變數。前面的遞迴因為前面有乘一個n，所以變成一定要下一層的東西算完，才知道這一層的結果是什麼，變成一定要遞迴下去。現在改寫版本前面沒有乘東西了，聰明的compiler最佳化就會把這遞迴展開，就變成寫起來是遞迴，跑起來不是遞迴。自己用visual studio c++ 2010試的結果，在release的設定下，上面的數字一大就會stack overflow，下面的不會（不過數字還是會overflow XD）。

還可以配合另外一個方法，如果有很多個地方要算階乘的話，那就建一個表，遇到沒算過的就重新算，然後把算出來的結果存起來，有算過的就直接丟答案出去，這樣會比較快。