1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive Algorithm, does it look correct

  1. Feb 29, 2016 #1
    1. The problem statement, all variables and given/known data
    1.PNG
    2. Relevant equations
    s1=1,sn=(sn-1) +n, and n>=2
    3. The attempt at a solution
    2.PNG
    It looks correct, but I'm not sure it'll work for negative values.
     

    Attached Files:

  2. jcsd
  3. Feb 29, 2016 #2

    RUber

    User Avatar
    Homework Helper

    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.
     
  4. Feb 29, 2016 #3

    Mark44

    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.
     
  5. Feb 29, 2016 #4
    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
  6. Feb 29, 2016 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Suppose you input n = 5. What output would your algorithm deliver?
     
  7. Feb 29, 2016 #6
    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...
     
  8. Feb 29, 2016 #7

    RUber

    User Avatar
    Homework Helper

    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.
     
  9. Feb 29, 2016 #8
    rec(just a name for the algorithm) {
    for( n=1; >=2; i++)
    ##S_n = S_{n-1}+n ##
    return ##S_n##
     
  10. Feb 29, 2016 #9

    RUber

    User Avatar
    Homework Helper

    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.
     
  11. Feb 29, 2016 #10
    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.
     
  12. Feb 29, 2016 #11

    Mark44

    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.
     
  13. Feb 29, 2016 #12

    Mark44

    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.
     
  14. Feb 29, 2016 #13
    Thank you, so if I started at n=2 the loop would start correct?
     
  15. Feb 29, 2016 #14

    RUber

    User Avatar
    Homework Helper

    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.
     
  16. Feb 29, 2016 #15

    RUber

    User Avatar
    Homework Helper

    When does the loop stop?
     
  17. Feb 29, 2016 #16

    Mark44

    Staff: Mentor

    Yes, but you should start with n = 1.
     
  18. Feb 29, 2016 #17
    So I should change the n>=2 to n>=1?
    Would it stop when the value of n is less than 1?
     
  19. Feb 29, 2016 #18

    Mark44

    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.
     
  20. Feb 29, 2016 #19
    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 ?
     
  21. Feb 29, 2016 #20

    RUber

    User Avatar
    Homework Helper

    @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



Similar Discussions: Recursive Algorithm, does it look correct
  1. Is this correct? (Replies: 5)

  2. Is this correct? (Replies: 1)

  3. Recursive sequence (Replies: 3)

  4. Is it correct or not (Replies: 4)

  5. Division Algorithm (Replies: 3)

Loading...