We're a community of 1.1M IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,080,599 Members — Technology Publication meets Social Media

Need help with recursion and arrays

Hey everyone. I actually have a homework assignment that is due Tuesday afternoon that I've been struggling all weekend with. The assignment is located at: http://cs.hofstra.edu./~cscsxd/hofstra/teaching/cs155-04/course_info/project/Recursion.cpp

As you can see, the function we have to write is:

``````int	*Rectangular_Shortest_Path(int startx, int starty, int endx, int endy,
int r[][6], int a[][6])
{
// please fill in your code here and remove the statement return -1;
// return -1;
}``````

I understand the algorithm to use in the sense that I can explain it on paper. But I am confused how to actually translate it into code given the professor's function prototype. What exactly are we returning as a pointer to an integer? Are we making changes to the two arrays that are passed in with each iteration?

From what I see, we are doing ...

Initially pass in 1,1 to start and 5,5 to end with both arrays
Try going to 1,2 and to 2,1, and decide which is better
After picking the one that is better, recursively go back to 1,1->1,2->1,3 or 2,2 ... and the same for the other coordinate ...

Oh wait, I'm screwed up again. Maybe I don't understand this at all :( It would be fantastic if someone could give me a hand with this, because I'm very confused. Thanks!

4
Contributors
11
Replies
5 Days
Discussion Span
8 Years Ago
Last Updated
12
Views
Dani
The Queen of DaniWeb
21,555 posts since Feb 2002
Reputation Points: 1,555
Skill Endorsements: 124

>What exactly are we returning as a pointer to an integer?
The shortest path, basically an array of x,y pairs.

>Are we making changes to the two arrays that are passed in with each iteration?
No, those arrays simply tell you what the distance between two points is.

>Try going to 1,2 and to 2,1, and decide which is better
Or you could walk each path in turn and collect the total distances. Then simply choose the shortest path from that collection. I'll leave it up to you to figure out if that's a good solution or not. ;)

Narue
Team Colleague
15,460 posts since Sep 2004
Reputation Points: 6,483
Skill Endorsements: 55

Hey there Narue. I spoke to my professor and it appears the reason I was stumped was because I misread the question!! It turns out we don't have to use recursion afterall! I have also opted to solve the problem in a similar way as you described (collecting distances one row at a time.) I'm working on the problem right now, and I'll have something that I can show here in about an hour.

Dani
The Queen of DaniWeb
21,555 posts since Feb 2002
Reputation Points: 1,555
Skill Endorsements: 124

We don't do your homework for you.

HA HA HA HA HA :-)

(Sorry, I couldn't resist)

Chainsaw
Posting Pro in Training
436 posts since Jun 2004
Reputation Points: 36
Skill Endorsements: 0

Muaha. Dani didn't ask for anyone to do her homework, only for hints to get started :)

Anyway, it's now almost 6 hours later and still nothing to show? ;)

jwenting
duckman
Team Colleague
8,558 posts since Nov 2004
Reputation Points: 1,674
Skill Endorsements: 19

Sorry, I have just been so busy I haven't had a chance to update this thread. I'm attaching what I have so far. It works up until the point where it populates the array that the function returns. In other words, it correctly computes the shortest path and prints it out as it goes. But then it screws up filling the data it computed into the array. At this point I'm just looking for some help finishing it up :) I'm pretty sure it's just a one-line typo somewhere in my last loop. If you run the file you should see what I'm talking about. Unfortunately, for some reason, I can get the thing to compile on my Windows machine in VS.NET but not by using gcc on my mac :( I think it's just some quirk.

Attachments Recursion.cpp (8.78KB)
Dani
The Queen of DaniWeb
21,555 posts since Feb 2002
Reputation Points: 1,555
Skill Endorsements: 124

I see a couple of things, though I can't claim to understand what is being attempted (heck, back in 1977 when I took CS classes, rectangles only had 3 sides! What we would have GIVEN for a 4-sided rectangle! You kids today... )

1) shortest_path is allocated at 8 ints (0.7) but you use 9 positions; n ends up as 9 (so 0..8 are filled in). Not exactly sure why, but....

2) you don't compute paths indexes 0 or 1 (0,0 0,1 1,0 1,1), yet you reference them when building shortest_path! Because you decrement the x or y value before fetching it to fill in shortest_path, you decrement x or y down to 0.

I moved setting shortest_path to the TOP of the while loop, and that seemed to help, but you still have to fix the setting of paths[] so it fills in the first entry (1,n and n,1)

(oh, and VC++ bitches about declaring x more than once)

(note: at some point you'll want to delete [] shortest_path in main())

(note: in cases where you use a simple 2 dimension array like this and don't want to add the complexity of a class or ugly macros, pick some size that is "larger than you'll ever need" (you picked 10 that might be fine), and then add asserts to make sure you don't blow the size. Here's an example:

static const int kArraySize = 10; // Naru would complain about static being deprecated, but heck this is my example code! :=)

assert( (endx < kArraySize) && (endy < kArraySize) ); // if this fires, kArraySize may need to be bumpped up!

int distance[ kArraySize ][ kArraySize ];

Chainsaw
Posting Pro in Training
436 posts since Jun 2004
Reputation Points: 36
Skill Endorsements: 0

Hey there Chainsaw. Thanks for the comments. As for deleting shortest_path in main ... the professor actually wrote that part. It was only our job to fill in the actual function. Also, since this program was mainly just to make sure we understood the algorithm, I'm not concerning myself with the technicalities of dynamically generating the array. But, yes, I used a size of [10][10] because that is larger than I ever plan on needing.

I'm actually confused what you mean where you say that I'm never computing the path indexes?

Dani
The Queen of DaniWeb
21,555 posts since Feb 2002
Reputation Points: 1,555
Skill Endorsements: 124

Here's a snippet of your code:

``````for (y=starty+1; y<=endy; y++)	// go down each column
{
for (x=startx+1; x<=endx; x++)	// go across each row
{
int distance_up = distance[x][y-1] + a[x][y-1];			// calculate weight to get to (x,y) from coordinate below it
int distance_right = distance[x-1][y] + r[x-1][y];		// calculate weight to get to (x,y) from coordinate to left of it
if (distance_up < distance_right)	// it's better to move up
{
distance[x][y] = distance_up;		// populate our distance array
path[x][y] = 1;						// populate our path array
cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
else								// it's better to move right
{
distance[x][y] = distance_right;	// populate our distance array
path[x][y] = 0;						// populate our path array
cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
}
}``````

x and y both go from 2..5 They skip 1! So path[1][y] and [x][1] values (10 total) are all random.

Chainsaw
Posting Pro in Training
436 posts since Jun 2004
Reputation Points: 36
Skill Endorsements: 0

And I wasn't advocating more complicated arrays, but you had this comment in the code:

// I could find no easy way to dynamically create a 2D array in C++

So I couldn't resist opening my big mouth about it. :-)

Chainsaw
Posting Pro in Training
436 posts since Jun 2004
Reputation Points: 36
Skill Endorsements: 0

Ahh! But if you look above that loop, you will realize that the first row and the first column of the matrix are populated each in their own individual loops, therefore taking care of [1][y] and [x][1]

Dani
The Queen of DaniWeb
21,555 posts since Feb 2002
Reputation Points: 1,555
Skill Endorsements: 124

true for distance[][] but not path[][].

Or am I smoking too much crack again?

``````for (x=startx+1; x<=endx; x++)
{
distance[x][starty] = distance[x-1][starty] + r[x-1][starty];
cout << "We went right to get to (" << x << "," << starty << ") in " << distance[x][starty] << " units" << endl;
}``````

path[x][starty] is set to, er, well, see, it's like this....

Chainsaw
Posting Pro in Training
436 posts since Jun 2004
Reputation Points: 36