The previous maze-solving examples Animate maze solving, version 1 and Animate maze solving, version 2 used a recursive method named `Solve` that returns an `IEnumerable` containing the paths that the program was searching.

# Removing Recursion

To remove the recursion, think about what happens during recursion or any method call for that matter. Here’s the structure of the `Solve` method.

private IEnumerable<List<MazeNode>> Solve( MazeNode end_node, List<MazeNode> path) { ... foreach (List<MazeNode> test_path in Solve(end_node, path)) yield return test_path; ... }

The method does a bunch of stuff and then uses a `foreach` loop to iterate over the paths returned by a recursive call to the `Solve` method. When the program makes that call, it saves the current call’s position and local variables. It then calls the method again passing it the desired end node and the path that we need to examine with a new node added at the end.

To remove the recursion, we can imitate those steps. In order to animate the solution, we also need to save that kind of state information and then later restore it so we can continue execution at the animation’s next step.

# The Solve Method

Here’s the new version of the `Solve` method.

private List<MazeNode> Path = null; private List<int> LastUsedNeighbor = null; // The final node in the Path list is the node we are visiting. // If LastUsedNeighbor has an entry for that node, then // we have visited some of its children. // See if we have a solution. // If not, try the last node's next neighbor. private void Solve() { // See if we have reached the end node. int last_node_index = Path.Count - 1; MazeNode last_node = Path[last_node_index]; if (last_node == EndNode) { FoundSolution = true; tmrStep.Enabled = false; return; } // See if the last node has any more neighbors we can visit. bool found_neighbor = false; int neighbor_index = LastUsedNeighbor[last_node_index]; MazeNode neighbor = null; for (; ; ) { // Try the next neighbor. neighbor_index++; // If we have checked all neighbors, break. if (neighbor_index >= last_node.Neighbors.Count) break; // See if this neighbor is not already in the current path. neighbor = last_node.Neighbors[neighbor_index]; if (!neighbor.InPath) { // Visit this neighbor. found_neighbor = true; LastUsedNeighbor[last_node_index] = neighbor_index; break; } } // See if we found a neighbor to visit. if (found_neighbor) { // Visit this neighbor. Path.Add(neighbor); LastUsedNeighbor.Add(-1); neighbor.InPath = true; } else { // We have visited all of the last node's neighbors. // Remove the last node from the Path list. last_node.InPath = false; Path.RemoveAt(last_node_index); LastUsedNeighbor.RemoveAt(last_node_index); } }

As before, the `Path` list stores the path we are currently exploring. The `LastUsedNeighbor` list holds the index of the last neighbor that we have considered for the last node in the path. When a “recursive” call returns, we use `LastUsedNeighbor` to decide which neighbor to explore next. If the current node has no more neighbors, then the “recursion” ends and control moves to the “calling method.”

The `Solve` method first checks to see if we have reached the maze’s destination node. If we have reached that node, the method sets `FoundSolution` to `true`, disables the `tmrStep Timer`, and returns.

If we have not yet found a solution, the method gets the index of the last neighbor visited. It then enters a loop to consider other neighbors of the current node. If the next possible neighbor index is greater than the current node’s neighbor count, then the code breaks out of the loop having found no new neighbor to use.

If the next neighbor considered is not currently in the test path, the code sets `found_neighbor` to `true` to indicate that we should use that neighbor. It adds the neighbor index to the `LastUsedNeighbor` list, and breaks out of the loop.

When the loop ends, the method checks whether it found a new neighbor to try. If it did find a neighbor, the code adds it to the `Path` list. It also adds -1 to the `LastUsedNeighbor` list to indicate that the last neighbor of this node is -1. That makes the `Solve` method’s loop starting looking for a new neighbor at index 0, which is this node’s first neighbor.

When the loop ends, if the method did not find a new neighbor to explore, then it must “move up” the “recursive call stack.” In that case, it removes the last node from the `Path` list because that node did not lead to a solution. It also removes the last entry from the `LastUsedNeighbor` list because we are done considering that node’s neighbors.

Now each time this method is called, it performs one step in the search for a complete path.

# Searching for a Solution

When the program needs to start finding a path through the maze, it executes the following `StartSolving` method.

// Start solving the maze. private void StartSolving() { // Remove any previous results. Path = new List<MazeNode>(); LastUsedNeighbor = new List<int>(); foreach (MazeNode node in Nodes) node.InPath = false; // Make the nodes define their neighbors. foreach (MazeNode node in Nodes) node.DefineNeighbors(); // Start at the start node. Path.Add(StartNode); LastUsedNeighbor.Add(-1); StartNode.InPath = true; // Solve. FoundSolution = false; tmrStep.Enabled = true; }

This method creates new, empty `Path` and `LastUsedNeighbor` lists and then defines the nodes’ neighbors as usual. It then adds the start node to the `Path` list and adds -1 to the `LastUsedNeighbor` list. It sets the start node’s `InPath` value to `true`, sets `FoundSolution` to false, and starts the `tmrStep Timer`.

When the timer’s `Tick` event fires, the following event handler executes.

// Take a step in solving the maze. private void tmrStep_Tick(object sender, EventArgs e) { Solve(); picMaze.Refresh(); }

This code calls the `Solve` method to take the next step searching for the solution. It then refreshes the `picMaze PictureBox` so its `Paint` event handler can display the current path.

# Conclusion

This example uses a timer to animate maze solving. Instead of using recursion, it uses the `Path` and `LastUsedNeighbor` lists to keep track of where it is in the process of finding a path through the maze. You can always remove recursion from any program if you try hard enough. In the worst case, you can imitate the recursion as this example does.

The previous version of the program used an enumerator created by a recursive method. The process of returning an enumerator is a bit strange and recursion can also be confusing, but personally I like that solution. It’s weird, but understandable once you figure out how to return enumerations.

Download the examples to see additional details and to compare their code.