How can I solve 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 the smallest integer value of the parameter x, so the return value is greater than 1.000.000?

Now I just do it by trial and error, and since this question is asked in paper format. I do not think that I will have enough time for trial and error. The question is how do you guys visualize this quickly so that it can be easily resolved. Thanks guys and I'm new to programming, so thanks in advance!

Answer 1

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 the math form,

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

Answer 2

( #):

public static void Main()
{
    int i = 0;
    int j = 0;
    do
    {
        i++;
        j = sum_down(i);
        Console.Out.WriteLine("j:" + j);
    } while (j < 1000000);
    Console.Out.WriteLine("i:" + i);
}
static int sum_down(int x)
{
    if (x >= 0)
    {
        return x - 1 + 2 * sum_down(x - 1);
    }
    else
    {
        return 1;
    }
}

, 2, 5, 12... , x-1, .

, :

i = 1 => sum_down ~= 4 (real is 2)
i = 2 => sum_down ~= 8 (real is 5)
i = 3 => sum_down ~= 16 (real is 12)
i = 4 => sum_down ~= 32 (real is 27)
i = 5 => sum_down ~= 64 (real is 58)

, , sum_down (x) ~ = 2 ^ ^{x + 1}. 2 ^ ^{x + 1} 1 000 000, 19.

Answer 3

, .

, :

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

,

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

( x x-1 x + 1 x, 1 )

x f (x):

x:    -1  0  1  2  3  4
f(x): 1   1  2  5  12 27

, , , :

x:    -1  0  1  2  3  4  
f(x): 1   1  2  5  12 27  
        0  1  3  7  15  

, x

f(x+1) - f(x) = 2^(x+1) - 1  
f(x+2) - f(x) = (f(x+2) - f(x+1)) + (f(x+1) - f(x)) = 2^(x+2) + 2^(x+1) - 2  
f(x+n) - f(x) = sum[0<=i<n](2^(x+1+i)) - n 

. a x=0, f(x+n) f(n):

f(x+n) - f(x) = sum[0<=i<n](2^(x+1+i)) - n  
f(0+n) - f(0) = sum[0<=i<n](2^(0+1+i)) - n  
f(n) - 1 = sum[0<=i<n](2^(i+1)) - n   
f(n) = sum[0<=i<n](2^(i+1)) - n + 1   
f(n) = sum[0<i<=n](2^i) - n + 1   
f(n) = (2^(n+1) - 2) - n + 1
f(n) = 2^(n+1) - n - 1  

.

Answer 4

:

int x = 0;
while (sum_down(x) <= 1000000)
{
    x++;
}

x , sum_down (x) 1.000.000.

: 19.

sum_down() , , , , , .

Answer 5

Python :

>>> from itertools import *   # no code but needed for dropwhile() and count()

Define a recursive function (see R Sahu answer)

>>> f = lambda x: 1 if x<0 else (x-1) + 2*f(x-1)

Then use the function dropwhile()to remove elements from the list [0, 1, 2, 3, ....] for which f(x)<=1000000, resulting in a list of integers for which f(x) > 1000000. Note: count()returns an infinite "list" of [0, 1, 2, ....]

The function dropwhile()returns a Python generator, so we use next()to get the first value of the list:

>>> next(dropwhile(lambda x: f(x)<=1000000, count()))
19