Convert this method from recursive to iterative

Question

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;
    }

Answer 1

I'll add somethings to your Node class

public class Node
{
    ......
    public Node PrevInPath{get;set;}
    public bool Visited {get;set;}
}

And (I think you want to find a path from source to destination), I suggest use Queue to find it simply, Also you should improve your data structure, currently your data structure is very poor and seems you code in functional language (not c#):

private List<Node> FindWayFrom(
        Node srcNode,
        Node dstNode,
        Graph graph)
    {

       foreach(var node in graph)
         node.Visited = false;

    Queue<Node> Q = new Queue<Node>();
    srcNode.PrevInPath = null;
    srcNode.Visited = true;
    Q.Enqueue(srcNode);

    while(Q.Count()>0)
    {
       var currNode = Q.Dequeue();
       if (currNode == destNode)
         break;

       foreach(var node in currNode.Adjacent)
       {
           if (node.Visited == false)
           {
               node.Visited = true;
               node.PrevInPath = currNode;
           }
       }

    }

    if (destNode.Visited)
    {
       var path = List<Node>();
       var currNode = destNode;
       while (currNode != srcNode)
       {
           path.Add(currNode);
           currNode = currNode.PrevInPath;
       }
       return path.Reverse().ToList();
    }
    return null;
}

Code is not tested may be has compile errors and is not as efficient as possible, but simply is fixable, but Idea is using queue, and marking visited node, also for tracking the path you should have some information about current created path, then going backward to output it.

Answer 2

You need to use a stack instead of calling the routine recusivly.

Place a while loop around the whole routine to check if your local stack has items if it does pop the item.

The line where you are calling the method again push those details onto the stack.

At the start of the routine push the incoming method details.

Answer 3

The most common way to do this is to push objects to the stack just as if you were making a function call, and operate on that stack inside the iteration

Way to go from recursion to iteration

Answer 4

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.

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.