How should I go about solving this recursion without trial and error

Question

int sum_down(int x)
{
    if (x >= 0)
    {
        x = x - 1;
        int y = x + sum_down(x);
        return y + sum_down(x);
    }
    else
    {
        return 1;
    }
}

What is this smallest integer value of the parameter x, so that the returned value is greater than 1.000.000 ?

Right now I am just doing it by trial and error and since this question is asked via a paper format. I don't think I will have enough time to do trial and error. Question is, how do you guys visualise this quickly such that it can be solved easily. Thanks guys and I am new to programming so thanks in advance!

Answer 1

The recursion logic:

x = x - 1;
int y = x + sum_down(x);
return y + sum_down(x);

can be simplified to:

x = x - 1;
int y = x + sum_down(x) + sum_down(x);
return y;

which can be simplified to:

int y = (x-1) + sum_down(x-1) + sum_down(x-1);
return y;

which can be simplified to:

return (x-1) + 2*sum_down(x-1);

Put in mathematical form,

f(N) = (N-1) + 2*f(N-1)

with the recursion terminating when N is -1. f(-1) = 1.

Hence,

f(0) = -1 + 2*1 = 1
f(1) =  0 + 2*1 = 2
f(2) =  1 + 2*2 = 5

...

f(18) = 17 + 2*f(17) = 524269
f(19) = 18 + 2*524269 = 1048556