- #1
Oh sorry that is my bracket,Mark44 said:@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.
Could you help with the algorithm?RUber said: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.
Kingyou123 said: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?
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?Ray Vickson said:Suppose you input n = 5. What output would your algorithm deliver?
rec(just a name for the algorithm) {RUber said: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.
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?Kingyou123 said:rec(just a name for the algorithm) {
for( n=1; >=2; i++)
##S_n = S_{n-1}+n ##
return ##S_n##
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.RUber said: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.
No. This is standard C notation for a for loop, but the loop body wouldn't execute at all.Kingyou123 said:I'm sorry, that was a typo, it's suppose to be for(n=1; n>=2; n++). Is that correct?
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 said:rec(just a name for the algorithm) {
Mark44 said: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.
Thank you, so if I started at n=2 the loop would start correct?Mark44 said: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.
When does the loop stop?Kingyou123 said:Thank you, so if I started at n=2 the loop would start correct?
Yes, but you should start with n = 1.Kingyou123 said:Thank you, so if I started at n=2 the loop would start correct?
So I should change the n>=2 to n>=1?Mark44 said:Yes, but you should start with n = 1.
Would it stop when the value of n is less than 1?RUber said:When does the loop stop?
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.RUber said:Using the ##S_n = S_{n-1}+n ## allows you to run a for loop without actually storing every member of the sequence.
So is the loop I've been working on incorrect? Should I have been using and if else?Mark44 said: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.
if ... else is the way to go, but you should start with the case when n is 1.Kingyou123 said: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 (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.RUber said:@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?
Mark44 said:if ... else is the way to go, but you should start with the case when n is 1.
Code:if (n == 1) (do something when n is 1) else if (n > 1) (do something else for larger numbers)
Mark44 said: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.
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 said:That's kind of the idea, but it isn't recursive.
Here's some C code that is recursive:
C:int add_recursive(int n) { if (n == 1) return 1; else if (n > 1) return add_recursive(n - 1) + n; }
A recursive algorithm is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. It involves breaking down a larger problem into smaller, more manageable subproblems until a base case is reached.
A recursive algorithm works by calling itself repeatedly until a base case is reached. Each time the function calls itself, it solves a smaller version of the original problem. Once the base case is reached, the function stops calling itself and returns the solution to the original problem.
A base case is a condition that, when reached, causes the recursive function to stop calling itself and return a solution. It is necessary to prevent the function from calling itself infinitely, also known as infinite recursion.
To determine if a recursive algorithm is correct, you can test it with different inputs and compare the results to the expected output. Additionally, you can use mathematical induction to prove the correctness of a recursive algorithm.
One advantage of using a recursive algorithm is that it can make code more concise and readable. It also allows for a more elegant solution to certain problems, particularly those that involve repetitive or self-similar structures. However, it is important to consider the potential for stack overflow and inefficiency when using recursion.