将此方法从递归转换为迭代 [英] Convert this method from recursive to iterative

问题描述

我有以下方法是递归的，但我得到的是StackOverflow，因为列表太长了。请有经验的人将这段代码转换为迭代？

I have the following method that is recursive, but I'm getting an StackOverflow because the list is too long. Please, someone with experience could convert this piece of code to iterative?

    private List<Node> FindWayFrom(
        Node srcNode,
        Node dstNode,
        List<Node> way,
        List<Node> visitedNodes)
    {
        if (visitedNodes.Contains(srcNode))
            return null;

        visitedNodes.Add(srcNode);
        way.Add(srcNode);

        IList connectedNodes = GetConnectedNodes(srcNode);

        if (connectedNodes == null || connectedNodes.Count == 0)
            return null;

        foreach (Node node in connectedNodes)
        {
            if (node == dstNode) return way;
            List<Node> result = FindWayFrom(node, dstNode, way, visitedNodes);

            if (result != null)
                return result;

            //It is not the correct way. Remove current changeset.
            way.Remove(node);
        }
        return null;
    }

推荐答案

这是一个快速尝试实施这个：

Here's a quick attempt to implement this:

public static class Router
{
  private class Frame
  {
    public Frame(Node node)
    {
      Node = node;
      NextChild = 0;
    }

    internal Node Node { get; private set; }
    internal int NextChild { get; set; }
  }

  /// <summary>
  ///  Finds a (but not necessarily the shortest) route from <paramref name="source" /> 
  ///  to <paramref name="destination" />.
  /// </summary>
  /// <param name="source"> Source node </param>
  /// <param name="destination"> Destination node </param>
  /// <returns> A list of nodes that represents the path from 
  ///  <paramref name="source" /> to <paramref name="destination" /> , including both 
  ///  <paramref name="source" /> and <paramref name="destination" /> . If no such path 
  ///  exists, <c>null</c> is returned. 
  /// </returns>
  public static IList<Node> FindFirstRoute(Node source, Node destination)
  {
    var visited = new HashSet<Node>();
    var path = new Stack<Frame>();
    path.Push(new Frame(source));
    var frame = path.Peek();

    while (frame != null)
    {
      if (frame.Node == destination)
      {
        return path.Select(x => x.Node).Reverse().ToList();
      }

      if (!visited.Add(frame.Node) || !DescendToNextChild(path, out frame))
      {
        frame = Backtrack(path);
      }
    }

    return null;
  }

  /// <summary>
  ///   Attempts to move to the next child of the node on top of the stack.
  /// </summary>
  /// <param name="path"> Current path </param>
  /// <param name="nextFrame"> Receives the new top frame in the path. If all children 
  ///  have already been explored, <paramref name="nextFrame" /> is set to <c>null</c> 
  /// </param>
  /// <returns> <c>true</c> if descending was successful, that is, if the current top 
  /// frame has any unexplored children left; otherwise, <c>false</c>. 
  /// </returns>
  private static bool DescendToNextChild(Stack<Frame> path, out Frame nextFrame)
  {
    var topFrame = path.Peek();
    var children = topFrame.Node.Children;
    if (children != null && children.Length > topFrame.NextChild)
    {
      var child = children[topFrame.NextChild++];
      path.Push(nextFrame = new Frame(child));
      return true;
    }
    nextFrame = null;
    return false;
  }

  /// <summary>
  ///   Backtracks from the path until a frame is found where there is an unexplored 
  ///   child left if such a frame exists.
  /// </summary>
  /// <param name="path"> The path to backtrack from. </param>
  /// <returns> 
  ///  The next frame to investigate, which is represents the first unexplored 
  ///  child of the node closest to the top of the stack which has any unexplored 
  ///  children left. If no such a frame exists <c>null</c> is returned and the search 
  ///  should be stopped. 
  /// </returns>
  private static Frame Backtrack(Stack<Frame> path)
  {
    Frame nextFrame = null;
    do
    {
      path.Pop();
    }
    while (path.Count > 0 && !DescendToNextChild(path, out nextFrame));

    return nextFrame;
  }
}

这是一个很好的脑筋急转弯和欢迎分心。虽然我没有彻底测试它，但我运行了不同的场景：没有路径存在，路径存在，循环存在，它们都返回了有效的结果。

It was a nice brain teaser and a welcome distraction. While I haven't tested it thoroughly I ran different scenarios: no path exists, path exists, loop exists, they all returned a valid result.

棘手的部分（概念上） ）是跟踪您当前正在下降的子路径。我将它存储在 Frame.NextChild 中。

The tricky part (conceptually) is to keep track of which child path you are currently descending into. I store this in Frame.NextChild.

更新：我重构了代码。主循环现在非常简单，两个主要概念（降序和回溯）现在很好地封装在不同的方法中。

Update: I've refactored the code. The main loop is now very simple and the two main concepts (descending and backtracking) are now nicely encapsulated in separate methods.

这篇关于将此方法从递归转换为迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！