Results 1 to 7 of 7
  1. #1
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Question Recursion problem

    I want to practice want I learned/didn't learn about recursion. I think I didn't learn much but I don't give up.
    Here I want to calculate n*n + (n-1)*(n-1) + (n-2)*(n-2) + ... etc. using recursion.
    Java Code:
    static long sum( int n ) {
            
            
            if( n == 0 )
                return 0; //base case
    
            else {
                
                return (n*n) + sum(n-1)*(n-1);
                            
            }

    I thought the above code was correct in order to give me the desired result but it is not. When I input for example 5 result is 317.
    I tracked variable n. It does go 5-4-3-2-1-0-1-2-3-4-5 but the result is not 55.
    Any ideas would be greatly appreciated.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,574
    Rep Power
    12

    Default

    return (n*n) + sum(n-1)*(n-1);

    That line doesn't look right. It's saying "figure out n squared, then add that to the sum of the squares up to (n-1) multiplied by (n-1)". Why that last bit?

  3. #3
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    That line doesn't look right. It's saying "figure out n squared, then add that to the sum of the squares up to (n-1) multiplied by (n-1)". Why that last bit?
    I thought it was supposed to be "n squared + (n-1) squared + (n-2) squared etc."
    Thanks, pbrockway2. I thought n*n is calculated once and doesn't go into the recursion. The recursion is little confusing to me but I'll keep practicing.
    Last edited by luke; 10-06-2010 at 02:05 AM.

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,574
    Rep Power
    12

    Default

    I'm not sure if you've got this problem solved or not. (And I am deliberately loathe to provide code as this would defeat the whole purpose of the question.)

    Here is your method rewritten with a more descriptive method name:

    Java Code:
    static long sumOfSquaresUpTo(int n) {
            if(n == 0)
                return 0; //base case
    
            else {
                
                return (n*n) + sumOfSquaresUpTo(n-1)   *(n-1);
                            
            }

    And I'm wondering if you can see why that last multiplication is wrong.

    After all the-sum-of-squares-up-to n is just n squared plus the-sum-of-squares-up-to (n-1).

  5. #5
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    I'm not sure if you've got this problem solved or not. (And I am deliberately loathe to provide code as this would defeat the whole purpose of the question.)

    Here is your method rewritten with a more descriptive method name:

    Java Code:
    static long sumOfSquaresUpTo(int n) {
            if(n == 0)
                return 0; //base case
    
            else {
                
                return (n*n) + sumOfSquaresUpTo(n-1)   *(n-1);
                            
            }

    And I'm wondering if you can see why that last multiplication is wrong.

    After all the-sum-of-squares-up-to n is just n squared plus the-sum-of-squares-up-to (n-1).

    My code is working with no problems now (thanks to your help). I understand why *(n-1) shouldn't be there. To me recursion is little tricky and that's why I need more practicing.

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,574
    Rep Power
    12

    Default

    Great. Glad to help.

  7. #7
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    Great. Glad to help.
    Thanks again, pbrockway2 :)

Similar Threads

  1. more fun... with recursion
    By sonny in forum New To Java
    Replies: 19
    Last Post: 03-23-2010, 06:09 AM
  2. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  3. recursion and call stack problem
    By OptimusPrime in forum New To Java
    Replies: 4
    Last Post: 12-26-2009, 10:49 PM
  4. Java Recursion Problem
    By gmnnn in forum Threads and Synchronization
    Replies: 1
    Last Post: 12-06-2009, 05:22 PM
  5. help with recursion
    By Nari in forum New To Java
    Replies: 15
    Last Post: 04-24-2008, 10:13 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •