如何在没有反复试验的情况下解决此递归问题

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;
    }
}

参数x的这个最小整数值是多少,因此返回值大于1.000.000？

现在我只是通过反复试验来做这件事,因为这个问题是通过纸质格式提出来的.我认为我没有足够的时间进行反复试验.问题是,你们如何快速想象这一点,以便轻松解决.谢谢你们,我是编程的新手,所以提前感谢!

Answer 1

递归逻辑:

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

可以简化为:

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

可以简化为:

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

可以简化为:

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

以数学形式,

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

与递归终止时N是-1.f(-1)= 1.

因此,

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