浅谈尾递归的优化方式

浅谈尾递归的优化方式2011-09-21 博客园 Jeffrey Zhao在上文《尾递归与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））;
}