# Recursive Algorithm, does it look correct

1. Feb 29, 2016

### Kingyou123

1. The problem statement, all variables and given/known data

2. Relevant equations
s1=1,sn=(sn-1) +n, and n>=2
3. The attempt at a solution

It looks correct, but I'm not sure it'll work for negative values.

#### Attached Files:

• ###### upload_2016-2-29_8-45-57.png
File size:
24.7 KB
Views:
36
2. Feb 29, 2016

### RUber

If n = 2, wouldn't Sn = 3?
I feel like you might want to use a for loop for this... something like:
S=1
for x = 2 to n
...
build the sum
...
Return to sum of n terms.

3. Feb 29, 2016

### Staff: Mentor

@Kingyou123, what you wrote is difficult to read. What did you write on the third line? It looks like Rec followed by a backwards 3. I have no idea what that means.

On the last line, the part in parentheses is Sn - 1 + n. I'm sure this means $S_{n - 1} + n$, but it looks more like S times n - 1 + n. The n - 1 part should be written as a subscript; i.e., lower than the preceding S.

4. Feb 29, 2016

### Kingyou123

Oh sorry that is my bracket,
rec(just a name for the algorithm) {
if(n==2)
return:1
return($S_{n - 1} + n$)
Could you help with the algorithm?

Last edited: Feb 29, 2016
5. Feb 29, 2016

### Ray Vickson

Suppose you input n = 5. What output would your algorithm deliver?

6. Feb 29, 2016

### Kingyou123

9... yeah, my mistake was thinking it would only run from 1 to 2. So if I place 5 in for Sn in $S_{n - 1} + n$ I get 4+5. I would have to simplify 5 to one 1. Could I just use (n-(n-1)? Like 5-(5-1) so that would give me 1 +sn which is 4. How would I write$S_{n - 1} + (n-(n-1)$ in code?
Edit never mind this...

7. Feb 29, 2016

### RUber

S_n = 1 + 2 + ... + n
means that
S_1 = 1
S_2 = 1+2 = 3
S_3 = 1+ 2 + 3 = 6
and so on.

So S_5 would be 15. It seems like to did not understand the notation of the problem.

Using the $S_n = S_{n-1}+n$ allows you to run a for loop without actually storing every member of the sequence.
Start with S = 1.
For x = 2 to n, you can just add x to S.
$S_2 = S_1 + 2$ becomes S = S + x in your loop.

If you want to keep all of the sums along the way, you can store them as an array.
Make S an array with n entries.
S(1) = 1, For x = 2 to n, S(x) = S(x-1) + x.
Or something like that.

8. Feb 29, 2016

### Kingyou123

rec(just a name for the algorithm) {
for( n=1; >=2; i++)
$S_n = S_{n-1}+n$
return $S_n$

9. Feb 29, 2016

### RUber

I am not sure what language you are using for the for loop. Does that mean for n = 1 to something greater than or equal to 2 counting by integers?
You will probably need to declare explicitly what the first member of your sequence is. Then you can add recursively to that.

10. Feb 29, 2016

### Kingyou123

I'm sorry, that was a typo, it's suppose to be for(n=1; n>=2; n++). Is that correct? the n++ would show the part where the value of the previous part is added.

11. Feb 29, 2016

### Staff: Mentor

No. This is standard C notation for a for loop, but the loop body wouldn't execute at all.

Here's why:
The initialization section (n = 1) is evaluated
The test section (n >= 2) is evaluated. Since n == 1, the expression n >= 2 is false, causing the loop to exit.
The update section (n++) is not evaluated in this circumstance.

12. Feb 29, 2016

### Staff: Mentor

What you wrote for a left brace -- the { character -- completely threw me off, as it doesn't look much at all like a brace. Also, you don't have a right brace at the end of your pseudocode.

13. Feb 29, 2016

### Kingyou123

Thank you, so if I started at n=2 the loop would start correct?

14. Feb 29, 2016

### RUber

Start small, make sure that if you feed your code n=2, your output will be 1+2=3, and input of n=3 gives output of 3+3=6.
It is important that you differentiate between your sum S, input n, and iteration variable.
What you are writing does not make those distinctions clear.

15. Feb 29, 2016

### RUber

When does the loop stop?

16. Feb 29, 2016

### Staff: Mentor

Yes, but you should start with n = 1.

17. Feb 29, 2016

### Kingyou123

So I should change the n>=2 to n>=1?
Would it stop when the value of n is less than 1?

18. Feb 29, 2016

### Staff: Mentor

But the problem statement asks for a recursive algorithm, which can be done without the use of a for loop, which I believe is the intent of this exercise.

19. Feb 29, 2016

### Kingyou123

So is the loop I've been working on incorrect? Should I have been using and if else?
if (n>=2)
(insert Sn here)
else
return answer ?

20. Feb 29, 2016

### RUber

@Mark44 aha! I did not appreciate that distinction until you pointed it out.
I am not particularly familiar with C++, but do you mean that the OP was very close to the right format, but declared S2 = 1 instead of S1 = 1?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted