Recursive Algorithm, does it look correct

[Kingyou123]

Homework Statement

Homework Equations

s1=1,sn=(sn-1) +n, and n>=2

The Attempt at a Solution

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

 

[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.

 

[Mark44]

@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.

 

[Kingyou123]

@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.

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

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.

Could you help with the algorithm?

 

[Ray Vickson]

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?

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

 

[Kingyou123]

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

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...

 

[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.

 

[Kingyou123]

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.

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

 

[RUber]

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

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.

 

[Kingyou123]

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.

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.

 

[Mark44]

I'm sorry, that was a typo, it's suppose to be for(n=1; n>=2; n++). Is that correct?

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.

 

[Mark44]

rec(just a name for the algorithm) {

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.

 

[Kingyou123]

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.

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.

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

 

[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.

 

[RUber]

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

When does the loop stop?

 

[Mark44]

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

Yes, but you should start with n = 1.

 

[Kingyou123]

Yes, but you should start with n = 1.

So I should change the n>=2 to n>=1?

When does the loop stop?

Would it stop when the value of n is less than 1?

 

[Mark44]

Using the $S_n = S_{n-1}+n$ allows you to run a for loop without actually storing every member of the sequence.

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.

 

[Kingyou123]

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.

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 ?

 

[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 S₂ = 1 instead of S₁ = 1?

 

[Mark44]

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 ?

if ... else is the way to go, but you should start with the case when n is 1.

if (n == 1)
   (do something  when n is 1)
else if (n > 1)
   (do something else for larger numbers)

 

[Mark44]

@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 S₂ = 1 instead of S₁ = 1?

His for loop header was correct as far as layout is concerned, but as written, the loop body would not have executed (I explained why). However, as the requirement is a recursive algorithm, a loop is not the right approach.

Hint to OP: the function doing the calculation should call itself. That's what recursive means.

 

[Kingyou123]

if ... else is the way to go, but you should start with the case when n is 1.

if (n == 1)
   (do something  when n is 1)
else if (n > 1)
   (do something else for larger numbers)

His for loop header was correct as far as layout is concerned, but as written, the loop body would not have executed (I explained why). However, as the requirement is a recursive algorithm, a loop is not the right approach.

Hint to OP: the function doing the calculation should call itself. That's what recursive means.

So is the proper code my professor asked for?

 

[Mark44]

That's kind of the idea, but it isn't recursive.

Here's some C code that is recursive:

int add_recursive(int n)
{
   if (n == 1)
      return 1;
   else if (n > 1)
      return add_recursive(n - 1) + n;
}

 

[Kingyou123]

That's kind of the idea, but it isn't recursive.

Here's some C code that is recursive:

int add_recursive(int n)
{
   if (n == 1)
      return 1;
   else if (n > 1)
      return add_recursive(n - 1) + n;
}

to correct my code I would just add the "add_recursice" part?

 

[Mark44]

Have you been taught to write recursive algorithms? Or how to write algorithms that take parameters?

I debated posting the code that I showed, as possibly being too much help. I decided to post it, as you were pretty close, but I didn't think you would be able to get how to make your algorithm recursive.

The code I showed is working code, but it assumes that the parameter n is a positive integer; i.e., n >= 1. I don't test for n == 0 or for n < 0.