C#递归本地函数

另一个使用本地函数的场景是递归调用,如下面使用 QuickSort 方法的示例所示。这里,本地函数 Sort 是递归调用的,直到集合排好序为止:.

public static void QuickSort<T>(T[] elements) where T : IComparable<T>
{
  void Sort(int start, int end) 
  {  
    int i = start, j = end;
    var pivot = elements[(start + end) / 2]; 
    
    while (i <= j)
    {
      while (elements[i].CompareTo(pivot) < 0) i++;
      while (elements[j].CompareTo(pivot) > 0) j--;
      if (i <= j)
      {
        T tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp; 
        i++;
        j--;
      }
    }
    if (start < j) Sort(start, j); 
    if (i < end) Sort(i, end);
  }

  Sort(0, elements.Length - 1);
}

在使用 C# 时,需要小心使用递归调用。下面的递归循环在大约24000次迭代之后,由于堆栈溢出而结束。C# 编译器不像 F#编译器那样实现尾调用优化。而使用尾调用优化,递归调用会转换为选代,以不消耗这个堆栈空间。

public static void WhenDoesItEnd()
{
  Console.WriteLine(nameof(WhenDoesItEnd)); 
  void InnerLoop(int ix)
  {
    Console.WriteLine(ix++); 
    InnerLoop(ix);
  }
  InnerLoop(1);
}