尾递归与Continuation

尾递归与Continuation2011-09-20 博客园 Jeffrey Zhao这几天恰好和朋友谈起了递归，忽然发现不少朋友对于“尾递归”的概念比较模糊，网上搜索一番也没有发现讲解地完整详细的资料，于是写了这么一篇文章，权当一次互联网资料的补充。

递归与尾递归

关于递归操作，相信大家都已经不陌生。简单地说，一个函数直接或间接地调用自身，是为直接或间接递归。例如，我们可以使用递归来计算一个单向链表的长度：

public class Node
{
  public Node（int value, Node next）
  {
    this.Value = value;
    this.Next = next;
  }

  public int  Value { get; private set; }

  public Node Next { get; private set; } 
}

编写一个递归的GetLength方法：

public static int GetLengthRecursively（Node head）
{
  if （head ==  null） return 0;
  return GetLengthRecursively（head.Next） + 1;
}

在调用时，GetLengthRecursively方法会不断调用自身，直至满足递归出口。对递归有些了解的朋友一定猜得到，如果单项链表十分长，那么上面这个方法就可能会遇到栈溢出，也就是抛出 StackOverflowException。这是由于每个线程在执行代码时，都会分配一定尺寸的栈空间（Windows系统中为1M），每次方法调用时都会在栈里储存一定信息（如参数、局部变量、返回地址等等），这些信息再少也会占用一定空间，成千上万个此类空间累积起来，自然就超过线程的栈空间了。不过这个问题并非无解，我们只需把递归改成如下形式即可（在这篇文章里我们不考虑非递归的解法）：

public static int GetLengthTailRecursively（Node head, int acc）
{
  if  （head == null） return acc;
  return GetLengthTailRecursively（head.Next, acc +  1）;
}