淺談尾遞歸的優化方式

在上文《尾遞歸與Continuation》裡，我們談到了尾遞歸的概念和示例，不過有些朋友對於尾遞歸的 功效依然有所懷疑。因此現在，老趙再簡單講解一下尾遞歸的優化原理，希望能給大家以一定理性認識。

尾遞歸的循環優化

尾遞歸，即是遞歸調用放在方法末尾的遞歸方式，如經典的階乘：

int　FactorialTailRecursion(int　n,　int　acc)
{
　　if　(n　==　0)　return　 acc;
　　return　FactorialTailRecursion(n　-　1,　acc　*　n);
}

由於遞歸在方法的末尾，因此方法中的局部變量已經毫無用處，編譯器完全可以將其“復用”，並把 尾遞歸優化為“循環”方式：

int　FactorialLoopOptimized(int　n,　int　acc)
{
　　while　(true)
　　 {
　　　　if　(n　==　0)　return　acc;

　　　　acc　*=　n;
　　　　n--;
　　 }
}

不過，上文還提到了尾遞歸中的常用技巧Continuation。那麼對於如下形式的Continuation，編譯器 又該如何優化呢？

int　FactorialContinuation(int　n,　Func<int,　int>　continuation)
{
　 　if　(n　==　0)　return　continuation(1);
　　return　FactorialContinuation(n　-　1,　r 　=>　continuation(n　*　r));
}