CODEWITHSUNDEEP
crecursion
Dennis
Dennis

Reputation: 939

Why does recursive function count downwards after peak?

with fear that I may overstep another question of mine (although this is a new problem alltogether) I still ask this question.

I have this code:

int blob_count(int y, int x, int gridCopy[][5], int sum){

    //Local vars
    int posX, posY;

    //Find the position 1 behind and 1 above the starting point, and start the loop there
    for(posX = -1;posX <=1; posX++){
        for(posY = -1; posY <= 1; posY++){
            if((y + posY) >= 0 && (x + posX) >= 0){
                if((y + posY) <= 5 && (x + posX) <= 5){
                    if(gridCopy[posY+y][posX+x] == 1){
                        //Set the starting point to 0 (so it wont get calculated again)
                        gridCopy[posY+y][posX+x] = 0;



                        y = posY+y;
                        x = posX+x;

                        sum++;
                        blob_count(y, x, gridCopy, sum);
                    }
                }
            }
        }
    }

    return sum;
}

The issue is that sum, which counts up 1, for each recursive run, returns the wrong value. By doing a print for each recursive run it gives the result:

sum = 1  
sum = 2  
sum = ...  
sum = n

Which is great, however, by setting printing out the sum outside the for loop (right before return sum;) the opposite happens when it has peaked, so it does this:

sum = n  
sum = ...  
sum = 2  
sum = 1  

return sum; // = 1

Which is obviously wrong, as I want the total count, not the lowest. Have I got the return value the wrong place? I've tried putting it in right after the recursive call (inside the loop), to no avail.

Upvotes: 0

Views: 150

Answers (2)

GrahamS
GrahamS

Reputation: 10350

Okay let's get rid of the extra bits and simplify your problem down to the essentials. You have:

int blob_count(int sum)
{
    sum++;

    if (sum < 10)
        blob_count(sum);

    return sum;
}

If you add printf("sum==%d\n", sum) right before the return then it will be called first at the innermost recursion (where sum == 10), then it will return to the next level out where sum == 9, print that, return to sum == 8 and so on.

If you put it before the recursive call to blob_count(sum) then you'll print the values before you recurse down, so they start with sum==0, sum == 1 and so on.

If you want sumto be the deepest level your recursion got to, then you could either pass it back via the return value like this:

int blob_count(int sum)
{
    sum++;

    if (sum < 10)
        sum = blob_count(sum);

    return sum;
}

or you could pass it via a pointer so that the original variable gets modified:

void blob_count(int* sum)
{
    *sum++;

    if (*sum < 10)
        blob_count(sum);

    return;
}

The first one is probably the solution you are looking for.

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183888

What pmg said. For each recursive call, the current value of sum is copied and the copy is passed to the recursive call. If you want to modify objects in functions, you must pass a pointer to these objects instead of the object itself.

Upvotes: 1

Related Questions