將遞歸轉換爲循環

Question

下面的C＃代碼計算了一組點的最小封閉圓，但由於它的遞歸實現而導致堆棧溢出異常。

它是從哪個a paper指定的算法遞歸萃取。

該算法是而不是尾遞歸，它並不平凡可轉換爲循環結構。

的遞歸函數是

public static Circle MiniDiskImpl(IReadOnlyList<Point2D> points, List<Point2D> boundary) 
{ 
    if (!points.Any() || boundary.Count == 3) 
    { 
     if (boundary.Count == 0) 
      return null; 

     if (boundary.Count == 1) 
      return null; 

     if (boundary.Count == 2) 
     { 
      var radius = boundary[0].DistanceTo(boundary[1])/2; 
      var center = (boundary[0] + boundary[1])*0.5; 
      return new Circle(Plane.XY, center, radius); 
     } 

     return new Circle(Plane.XY,boundary[0],boundary[1],boundary[2]); 
    } 

    var p = points[0]; 
    var Q = points.GetRange(1,points.Count - 1); 
    var D = MiniDiskImpl(Q, boundary); 

    if (D==null || D.Center.DistanceTo(p) >= D.Radius) 
    { 
     D = MiniDiskImpl(Q, boundary.Concat(p).ToList()); 
    } 

    return D; 
} 

用戶調用此函數。

public static Circle MiniDisk(List<Point2D> points) 
{ 
    points = points.Slice(0); // Clone the list so we can manipulate in place 
    points.Shuffle(); // sorted points cause poor algorithm performance 
    return MiniDiskImpl(points, new List<Point2D>()); 
} 

問題是，使算法不遞歸需要什麼轉換？

Answer 1

我只是驚歎以下。

/// <summary> 
/// Find the smallest enclosing circle. See reference 
/// http://www.inf.ethz.ch/personal/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf 
/// "Smallest enclosing disks (balls and ellipsoids) EMO WELZL 
/// </summary> 
/// <returns></returns> 
public static class Circles 
{ 

    private static Return<Circle> Left 
     (List<Point2D> points, List<Point2D> boundary) 
    { 

     if (!points.Any() || boundary.Count == 3) 
     { 
      if (boundary.Count <= 1) 
      { 
       return Return.Value<Circle>(null); 
      } 

      if (boundary.Count == 2) 
      { 
       var radius = boundary[0].DistanceTo(boundary[1])/2; 
       var center = (boundary[0] + boundary[1]) * 0.5; 
       return Return.Value(new Circle(Plane.XY, center, radius)); 
      } 

      return Return.Value(new Circle(Plane.XY, boundary[0], boundary[1], boundary[2])); 
     } 

     var p = points[0]; 
     var q = points.GetRange(1, points.Count - 1); 

     return from circle in Return.Call(() => Left(q, boundary)) 
       from result in 
        (circle == null || circle.Center.DistanceTo(p) >= circle.Radius) 
          ? Return.Call(() => Left(q, boundary.Concat(p).ToList())) 
          : Return.Value(circle) 
       select result; 
    } 

    public static Circle MiniDisk(List<Point2D> points) 
    { 
     points = points.Slice(0); 
     points.Shuffle(); 
     return TrampolineRecursion.Do(()=>LeftLeft(points, new List<Point2D>())); 
    } 

} 

使用下面的蹦牀monad的實現我只是magicked了。

namespace Weingartner.Numerics.Recursion 
{ 
    public class Return<T> 
    { 
     #region return value mode 
     public bool HasReturnValue; 
     public T ReturnValue; 
     #endregion 

     #region call and continue mode 
     public Func<Return<T>> Call; 
     public Func<T, Return<T>> Continue; 
     #endregion 

     /// <summary> 
     /// To avoid GC pressure we use a thread static variable 
     /// to handle the return value from functions. 
     /// </summary> 
     [ThreadStatic] private static Return<T> _ReturnRegister; 

     public static Return<T> R() 
     { 
      if (_ReturnRegister == null) 
      { 
       _ReturnRegister = new Return<T>(); 
      } 
      return _ReturnRegister; 
     } 

     public Return<T> Bind(Func<T, Return<T>> fn) 
     { 
      if (HasReturnValue) 
       return Return.Call(() => Return.Value(ReturnValue), fn); 

      if(Continue!=null) 
       return Return.Call(Call, t => Continue(t).SelectMany(fn)); 

      return Return.Call(Call, fn); 
     } 

     public Return<T> SelectMany(Func<T, Return<T>> fn) 
     { 
      return Bind(fn); 
     } 
     public Return<T> SelectMany(Func<T, Return<T>> f, Func<T, T, T> g) 
     { 
      return Bind(x => f(x).Bind(y => Return.Value(g(x, y)))); 
     } 

     public Return<T> Select(Func<T, T> fn) 
     { 
      if (HasReturnValue) 
       return Return.Value(fn(ReturnValue)); 

      if(Continue!=null) 
       return Return.Call(Call, t => Continue(t).Select(fn)); 

      return Return.Call(Call, t => Continue(t).Select(fn)); 
     } 

     public T Run() 
     { 

      var stack = new Stack<Func<T,Return<T>>>(); 
      if(Continue!=null) 
       stack.Push(Continue); 
      stack.Push(r => Call()); 

      var @return = Return.Value(default(T)); 

      while (stack.Count > 0) 
      { 
       @return = stack.Peek()(@return.ReturnValue); 
       stack.Pop(); 
       if (!@return.HasReturnValue) 
       { 
        if(@return.Continue!=null) 
         stack.Push(@return.Continue); 
        var t = @return; 
        stack.Push(r => t.Call()); 
       } 
      } 

      return ReturnValue = @return.ReturnValue; 
     } 
    } 

    public class Return 
    { 
     public static Return<T> Value<T>(T t) 
     { 
      var r = Return<T>.R(); 
      r.HasReturnValue = true; 
      r.ReturnValue = t; 
      return r; 
     } 

     public static Return<T> Call<T> 
      (Func<Return<T>> call, Func<T, Return<T>> @continue = null) 
     { 
      var r = Return<T>.R(); 
      r.HasReturnValue = false; 
      r.Call = call; 
      r.Continue = @continue; 
      return r; 
     } 

    } 

    public static class TrampolineRecursion 
    { 
     public static T Do<T>(Func<Return<T>> call) 
     { 
      return Return.Call(call).Run(); 
     } 
    } 
} 

Answer 2

當你使用遞歸，你利用調用堆棧來執行的東西，你可以隨時通過刪除自己的對象，以實際堆棧變換遞歸算法到它的迭代版本，請參見維基DFS例如：http://en.wikipedia.org/wiki/Depth-first_search