Algorithm question...

[scootermaster]

I know we all hate recursion -- well, those of use weened on C/C++ do. Those wackos who grew up on Lisp must love it! -- but I have a question that's been nagging at me that I can't seem to solve (and no, it's not for homework).


So I have this graph structure (it's a DAG; directed acyclic, for the rest of you) and I want to return a couple of values up "through" the recursion stack; that is to say, I want to do a DFS from a certain node, until I hit a pre-defined stopping point (in this case, either a "matching" node or the sink) and then return two values: the hop count from the start to finish, and the aggregate cost to get there.

I'm just having problems getting the recursive function to return the right value to it's preceding calls, and then having the preceding calls aggregate the totals correctly, etc (it's tough to figure out what needs to be passed in as a parameter to the recursive call, what can be local, what needs to be local, what has to be passed by reference, and what needs to be returned, since each call is going to have it's own copies of things, and of course, there's C's friend parameter passing semantics).

If you want more details about what I'm actually doing -- if you're into that sort of thing -- I can get into it.

Any ideas?

 

[DaveSimmons]

The easiest way might be to pack both into a single int or double so you can make it the return value of the recursive call:

int irecurseu ( int parenthops, int parentcost )
{ }

// pack
int pack = (hops * 100 000) + cost

// unpack
int hops2 = pack / 100 000
int cost2 = pack % 100 000

If that isn't suitable you'll probably need to "new" or "malloc" a response struct at each nesting level to return to the caller (which frees it), or possibly only create it at the lowest level then pass it up to the top to be freed. This is going to be harder to get right.

 

[Markbnj]

As Dave said, either pack it into an int, or possibly return a small struct. Otherwise you will have to get the data off the stack and into a static variable. Tracking recursion depth is a pretty common task, so Google should provide a few ideas as well.

If you want to do it automatically write a small class like this:

class RecursionDepth
{
static int depth = 0;

public static int Depth() { int t = depth; depth = 0; return t; }

public RecursionDepth() { depth++; }
}

And then just toss a local instance of it at the beginning of the recursed function. Sorry for any syntax problems; I don't do much C++ anymore. I'm sure you get the idea. Inline the methods so that there is no added overhead. It's just a syntactic convenience.

 

[jman19]

I'd just pack the return values in an object.

 

[scootermaster]

Originally posted by: jman19
I'd just pack the return values in an object.

Well, the issue isn't really with how to store the return value(s), but more with how to compute them and return them up through the recursive call stack, given C's wonderful (ha) parameter passing semantics.

For example:

DFS(node, hopcount, total)


if (!node.visited)
for each successor
DFS(node, hopcount++, total+=node.value)


I'm pretty sure this doesn't work, because of the parameter semantics.

I could -- as suggested -- make the hopcount/etc thing a global and increment it that way, but that seems inelegant, and just on principle I think it should be able to be done using parameters and return values. But I think it requires use of some local values and incrementing the hop count on the return, not on the call (as above).

Anyway, does the general point is that the issue is not how to appropriately store the values, but how to get at them and increment them appropriately as you go up and down the recursive call stack. Any more thoughts?

 

[DaveSimmons]

I don't think it matters whether you increment the hopcount in the caller or callee if you just need the total trip cost and don't need to keep the cost along the path.

Your pseudocode is missing the int return from the successors, it should be

besthops = infinite
bestcost = infinite // some magic number like 99 999
// change to current total if this is a match / valid endpoint

if (!node.visited)
for each successor
{
childpackreturn = DFS(node, hopcount++, total+=node.value)
Then you unpack and I assume you update bestcost if lower one found, and if ties then the lowest hopcount.
}

mypackreturn = // pack bestcost and besthops
return mypackreturn ;

This should work without any globals or struct for the problem as you've described it. If the packed return to the initial call is a cost of "infinite" then no path was found within any hop or cost limit that you set.


If you really need a struct, for a different problem than what you've described, as I mentioned earlier you would malloc or new it at the deepest level of recursion then free or delete it at the right time at a higher level. In the example above you might immediately free all but the best of the successors and return the winner. Your function would be:
mystruct* DFS( node, hop, total )

If you need to build a list of nodes visitied for the shortest path, or an overall map of costs between nodes those might require adding the total for the current node in the calee, only after adding up the total of the successor nodes.

Also, if this is a homework problem it's often best to list the exact requirements from the assignment, the describing which parts you don't understand or can't figure out.

 

[jman19]

Bah just posted a reply but the internets ate it.

Anyway, don't use a global variable, and your pseudocode is odd - you're not actually returning anything.

If I remember to later I'll try to post a solution - though Dave might have the right idea, I haven't read his post.

 

[scootermaster]

Originally posted by: jman19
Bah just posted a reply but the internets ate it.

Anyway, don't use a global variable, and your pseudocode is odd - you're not actually returning anything.

If I remember to later I'll try to post a solution - though Dave might have the right idea, I haven't read his post.

I hate when that happens. I'm going to try some of these hints. Any more ideas?

 

[KCfromNC]

If you're doing this in C, it'll have to be something like

DFS(NODE node, int *hopcount, int *total)


if (!node.visited)
for each successor
*hopcount += 1;
*total += node.value;
DFS(node, &hopcount, &total)

Probably want to rethink passing node as a non-pointer as well, but that's the general idea for passing junk using C.

Using C++, it'd be int &hopcount and int &total in the function prototype and no need to treat the vars as pointers in the function, but the idea's the same.

 

[DaveSimmons]

^ that could work too, but you'll need to reset the values of hopcount and total before calling DFS on each successor. Otherwise the values will be the cost of taking every path at once.

With recursion It's always good to run your algorithm on paper to see exactly where it goes horribly wrong 🙂