c++: using a deque for recursion?

R

Ragnafrak

Contributor
Veteran X
I have an assignment that asks me to do this. This is the only part I have to worry about, was wondering if any of you CS/IST/etc majors have ever done this in a class.

the deque will be used with vector to simulate recursion while solving a maze
 
be careful of the stl... it's not copied during recursion. so if you modify it while recursing, it's going to stay modified for previous/subsequent recursive levels.
 
i won't be using any recursion tho.. what i'm supposed to do is make it iterative with a deque to simulate recursion.. i just have no idea how to do this
 
i store the maze in a vector.. then in some way use the deque to iteratively end at the right point..

i load a text file that has the dimensions of the maze, the maze itself, 1s as pathways, 0s as walls

it also tells me the exact start position and end position
 
Simulate recursion?

Basically you're implementing your own function call stack? Dunno how that would be a que, but a stack, from what I understand from your problem.

Cuz recursion goes back first... you walk out of each function call from most recent (LIFO)
 
I wouldn't know how to do that without keeping track of which spaces you've visited in a seperate vector; is that allowed?

I wrote a program that solved (4-dimensional!) mazes using recursion, and simulating recursion with a deque is pretty easy, so...
 
alright i'll just post the whole assignment lol..

Redo the maze search project in Chapter 4 without using recursion in the tryToSolve method. In other words, use an iterative method that uses a deque to simulate recursion. The original version of the project is accessible from the Source Code link on the book's website. You do not have to use the code from chapter 4, you can write your own code.

The input for this program will be a file, maze.txt, that contains the following info:
1st line: two fields, number of rows and number of columns, relative to 1, in the maze.
2nd line: starting position for the path (row, column, relative to 0).
3rd line: ending position for the path (row, column, relative to 0).
The remaining lines of the file are the values for the corridors and walls of the maze in a row by row format. (1 represents a corridor, 0 represents a wall).
This file can be found in the Maze Program Files folder.

The maze must be stored in a two dimension vector. A deque must be used to simulate the recursion. Do not use any arrays in your program. Your program should print out a message each time it tries a new path and print out a message each time it backtracks. At the end, the program should print out the complete path found. Sample output can be found in the Maze Program Files folder. You may want to write your output to a text file as the output will scroll off the cout window.
The code from the text uses classes, but you are not required to use classes in your program implementation. Once again, if you have more than one file to submit, they must be zipped together, if you have only one .cpp file, it can be submitted by itself.
Note: Make sure your program indicates when a maze is unsolvable.
Click to expand...
 
so far i've got the file loaded (duh).. the two-dimensional vector setup, all the output stuff done, etc.. just don't know how they want me to use this deque.. i was thinking originally to setting the size of the deque to something related to the start/end x,y differences in the start/end points.. so it would continue until the maze is navigated horizontally and vertically
 
What they want you to do is use the deque to store your variables, just as would be done implicitly with recursion.

Code: 
void func() {
  while(!solved) {
    /* do my work for this "recursive frame" */
    deque.push_back(my data for this recursive frame);
    /* update variables in preparation for next "recursive call" */
  }
}
 
I guesso... anything you'd have previously relied on recursion to handle ;)

So as you travel the maze, you previously probably called your traverse() with an x/y coord, examined that coordinate to determine the next step, then called traverse() with the next step coordinates. Now, you want to stored these coords on the stack so that as you do this iteratively, you have your path traced out on the stack.
 
use the deque to store the path you are attempting to take within the maze

when you get to a split, mark that position as special. then try the first path, if it is a dead end, back track (pop values off) until you return to the split, then try the 2nd path, ad infinitum.
 
try this code snippet:

Code: 
void func() {
    maze.init()
    while(!maze.solved()){
        maze.turn_right();
    }
    maze.free();
}
 
crazybob, recursive maze solving doesn't use turning... it basically just branches out in all possible directions until it finds the path
 
You must log in or register to reply here.
Back
Top