🔒 Locked

recursion with reference parameter

Started by sooner123 Dec 20, 2012 at 10:36 AM 4 replies 1.7k views

Original Post

Dec 20, 2012 at 10:36 AM

So I have this function that recursively flows through a tree of vectors of pointers to Locations. Notice the reference parameter int&total

[source lang="cpp"]int score(Location* locationToScore, int&total){
total++;
int n = locationToScore->explored?1:0;
for (int i=0; isubLocations.size(); i++) n += score(locationToScore->subLocations, total);
return n;
}[/source]

I call this function like this:

[source lang="cpp"]int total = 0;
cout << score(sol, total) << "/" << total;[/source]

But it keeps displaying the total as 0.

Just to make sure I was doing it right I made a simpler program to test it and it works fine in the test program but I can't see a difference:

Test program:
[source lang="java"]#include

using namespace std;

int testFunction(int x, int&y){
y++;
if (x==0) return 1;
else return 1 + testFunction(x-1, y);
}

int main(){
int y = 3;
cout << testFunction(3, y);
cout << y;
}[/source]

Brother Bob

Dec 20, 2012 at 10:48 AM

You keep adding up the values depending on locationToScore->explored, but you never change the explored-member anywhere so my guess is that all of them are false and thus you keep adding up zeros all the time.

sooner123

Dec 20, 2012 at 10:57 AM

Actually the explored is outputting correctly. It's the reference parameter, total, that's giving me trouble.

Brother Bob

Dec 20, 2012 at 10:58 AM

Actually, scratch that, I was so focused on the return value from the score function that I didn't see that you actually print the value of total after that.

The reason is the order of evaluation of parameters within an expression. The language does not specify the order in which sub-expressions within an expression are evaluated. In this case, you have two sub-expressions that causes the problem:

The value of the function call to score.
The value of total.

The language does not specify the order in which these two sub-expressions are evaluated. If the value of total is evaluated before the function call, then the value of total results in zero, and then the function is called, setting it to its new value. In essence, you have two expressions where one (the value of total) depends on the other (the function call), and where the one expression has a side effect on the other expression. Your program is not well formed.

You need to call the function and grab its return value before printing it to ensure that the function is actually called before printing the value of total.


 int total = 0;
 int myscore = score(sol, total);
 cout << myscore << "/" << total;

sooner123

Dec 20, 2012 at 11:01 AM

That did it. Thanks!

It had vaguely occurred to me that this might be the case, but I ignored myself.

Sandman

Dec 20, 2012 at 11:10 AM

I call this function like this:

int total = 0; cout << score(sol, total) << "/" << total;

But it keeps displaying the total as 0.

Your recursive function is probably working fine: this line of code is the problem.
The order of evaluation for parameters passed to cout using the << operator is effectively undefined. For various reasons, it is most likely evaluating them in the opposite order to that which you expect - it's printing the value of total first, (which is initially zero) and THEN calling the score function.

Note in your test program, you are outputting the return value of the function, and the value returned by reference in different cout calls. This works exactly as you expect.

Try using separate cout calls or call the score function outside of cout, e,g:


 int total = 0;
 int currentScore = score(sol, total);
 cout << currentScore << "/" total;

e;fb

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.