Question

I call sum(5);

public static int sum(int n){
if(n<2)
return 0;
else
return sum(n-1)+2*n;
}


I know 28 is returned.
The first thing that happens is sum(5-1) + 2*n
2*n is left over for later, right? I'm not sure, but I know that n equals 4 now.
sum(4-1) and now n=3
sum(3-1) and now n = 2
sum (2-1) and now n = 1 and we go to the base case.
The base case returns 0, so go back to sum(2)+2*n and plug in 0 for n, which is 2.
Now go to sum(3) + 2 * n, plug in 2 for n. We get 7.
Now go to sum(4) + 2 * n, plus in 7 for n. We get 18.

I am off by 10. How do I do this properly?

Answer 1

@pre-algebra If you're still here

Answer 2

Sum(5)
= Sum(4) + 2^5
= Sum(3) + 2^4 + 2^5
= Sum(2) + 2^3 + 2^4 + 2^5
= Sum(1) + 2^2 + 2^3 + 2^4 + 2^5
= 0 + 4 + 8 + 16 + 32
= 60

Answer 3

What? It supposed to be 28

Answer 4

the first one already 2^5 = 32

Answer 5

You have the function:

public static int sum(int n)
{
if (n < 2)
return 0;
else
return sum(n - 1) + 2 * n;
}

If you call sum(5), this is what happens:

1. sum(4) + 2 * 5 is computed.
2. sum(3) + 2 * 4 is computed.
3. sum(2) + 2 * 3 is computed.
4. sum(1) + 2 * 2 is computed.
5. 0 is returned.
6. 0 + 2 * 2 (4) is returned.
7. 4 + 2 * 3 (10) is returned.
8. 10 + 2 * 4 (18) is returned.
9. 18 + 2 * 5 (28) is returned.
10. The recursion terminates, and 28 is returned.

Answer 6

Mathematically, this function can be represented as\[2\sum_{i=2}^{n}i=n(n+1)-2.\]

Answer 7

This is why mathematics is so beautiful: This particular problem can have three different implementations:

// mathematical version
int sum(int n)
{
return n * (n + 1) - 2;
}

// iterative version
int sum(int n)
{
int sum = 0;
for (int i = 2; i <= n; i++)
sum += i;
return 2 * sum;
}

// recursive version
int sum(int n)
{
if (n < 2)
return 0;
else
return sum(n - 1) + 2 * n;
}

You be the judge!

Answer 8

@pre-algebra Wow, you are real genius mind! I wish I had that fantastic machine in mine :)