13820

Convert this method from recursive to iterative

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

Answer1:

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.

Answer2:

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.

Answer3:

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

Answer4:

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.

Recommend

  • jQuery datatables - difference between fnGetNodes() and fnGetData()?
  • Logging into a Django server with Cypress.io
  • How to serialize class hierarchies whose classes refer to each to other, but avoiding XmlInclude?
  • 2d array, all values are adjacent
  • Shortest path in a grid
  • What products support 3-digit region subtags, e.g., es-419 for Latin-American Spanish?
  • How do I add a File Type Association in a Windows Phone 8.1 app manifest?
  • Is there any way to call saveCurrentTurnWithMatchData without sending a push notification?
  • Angular Bootstrap Carousel Slide Transition not working correctly
  • Where these are stored?
  • Suppressing passwd when calling sqlplus from shell script
  • Silverlight DependencyProperty.SetCurrentValue Equivalent
  • wxPython: displaying multiple widgets in same frame
  • ADO and msqli connections very slow
  • How to add git credentials to the build so it would be able to be used within a shell code?
  • Groovy: Unexpected token “:”
  • Caching attributes in superclass
  • Display images in Django
  • Problem deserializing objects from cache on MyBatis 3/Java
  • How to create a file in java without a extension
  • Is it possible to access block's scope in method?
  • jQuery .attr() and value
  • Scrapy recursive link crawler
  • SignalR .NET Client Invoke throws an exception
  • R - Combining Columns to String Based on Logical Match
  • Azure Cloud Service Web Role web pages do not load
  • script to move all files from one location to another location
  • MySQL WHERE-condition in procedure ignored
  • ILMerge & Keep Assembly Name
  • Symfony2: How to get request parameter
  • Run Powershell script from inside other Powershell script with dynamic redirection to file
  • How to delete a row from a dynamic generate table using jquery?
  • Revoking OAuth Access Token Results in 404 Not Found
  • WPF Applying a trigger on binding failure
  • using HTMLImports.whenReady not working in chrome
  • embed rChart in Markdown
  • Authorize attributes not working in MVC 4
  • EntityFramework adding new object to nested object collection
  • Unable to use reactive element in my shiny app
  • How to push additional view controllers onto NavigationController but keep the TabBar?