Results 1 to 15 of 15
Like Tree1Likes
  • 1 Post By nellac77

Thread: Simple Recursion

  1. #1
    nellac77 is offline Member
    Join Date
    Sep 2014
    Posts
    2
    Rep Power
    0

    Default Simple Recursion

    Hi,

    I am new to Java, and programming, in general. I have not had a problem with mathematical induction with my educational background, but I am having difficulty with basic recursion.

    I have an assignment that wants me to write a Java function based on induction to determine how many numbers in an array have a value greater than, or equal to, 100.

    I have started with:

    Java Code:
    int recurseHundred (int [] A, int n) {
         //n is the number of elements in the array.
    
         //Base case:
         if (n == 1 && n >= 100) return A[0];
    
         //Recurse
         int num = recurseHundred(A, n-1);
         if (n-1 >= 100) return A[n-1];
              else return num;
    }
    I don't think this actually does the trick. Can anyone offer some advice?

    Thanks!

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,143
    Rep Power
    14

    Default Re: Simple Recursion

    Look at this line:

    if (n == 1 && n >= 100)

    When will it ever be true?

    Then look at this line:

    return A[n-1];

    Why are you ever returning an element from the array, when what you want is a count?
    How to Ask Questions the Smart Way
    Static Void Games - GameDev tutorials, free Java and JavaScript hosting!
    Static Void Games forum - Come say hello!

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Simple Recursion

    If there are no (more) numbers in the array, the result equals zero; otherwise check the current number at position i and compute the number of numbers > 100 in the rest of the array; add either zero or one to that number (depending on the check of the current number).

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  4. #4
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Simple Recursion

    I picked up recursion when I started at a site called codingbat.com
    The exercises there were really good for teaching recursion. Once you see the pattern, it becomes very easy.

    This recursion is very simple.
    First of all, lets determine what variables you need.

    Of course you need the array itself, A[]. Then, you need to have an index, to see which number in the array you're looking at. Finally, you need a variable to count up how many number are greater than 0.

    So, our function will look like this:
    Java Code:
     
    public int recurseHundred(int[] A, int index, int numberCount) {
    
    }
    The first line that we will put in our code is a check to know when to stop. When are you done cycling? When the index reaches the length of the array, of course! So our first line will be:
    Java Code:
    if(index >= A.length - 1) return numberCount;
    If we AREN'T at the end yet, than we have numbers to check! So....
    Java Code:
    if(A[index] >= 100) {
        return recurseHundred(A, index + 1, numberCount + 1);
    } else {
        return recurseHundred(A, index + 1, numberCount);
    }
    If the number is greater than or equal to 100, return the number array, the index + 1, and the number count + 1. Otherwise return A, index + 1, and the same number count. You'll always want to return the same number array - of course, since you need that number array to check the numbers - and always increase the index by 1 to signify that you've checked the current index. If the number is greater than or equal to 100, then you add to the counter, if not, keep going without adding!

    It is very simple once you get the hang of it. First you need to figure out what the variables you'll need in your method are. Then, you need to figure out when to stop - more formally known as the base case. Finally, figure out what you're checking and add or don't add to the counter when needed. It is as simple as that!

    The final method, all put together:
    Java Code:
    public int recurseHundred(int[] A, int index, int numberCount) {
         if(index >= A.length - 1) return numberCount;
         if(A[index] >= 100) {
              return recurseHundred(A, index + 1, numberCount + 1);
         } else {
              return recurseHundred(A, index + 1, numberCount);
         }
    }
    Now think through this to see how it works. Imagine the function going through each index 1 by 1, adding 1 to the counter if the current index is greater than or equal to 100, otherwise not adding anything. Once it reaches the end of the array, the index must equal the length of the array - 1, so we don't recurse again, and build back up.

    Again, I recommend codingbat.com to learn recursion. The problems on there are really good for this sort of thing.

  5. #5
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Simple Recursion

    Why are you passing numberCount as an argument? It's not needed. The OP had the correct method signature before your
    explanation.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  6. #6
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Simple Recursion

    That is the way I was taught and how I've seen it done. The array itself, an index variable, and a counter. Maybe the OP had it correct as well. There are lots of different ways to do this. In fact, I don't see anything wrong with having a counter there.

    I find the way I did it the best way in my experience as it makes the most sense and is easiest to follow, especially for the first time.

    I guess you could return 1 + function(A, index + 1) but does it honestly matter that much?
    Last edited by AlexGraal; 09-11-2014 at 01:59 AM.

  7. #7
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Simple Recursion

    Quote Originally Posted by AlexGraal View Post
    I guess you could return 1 + function(A, index + 1) but does it honestly matter that much?
    To me, it does. Although I am certainly not an expert in recursive algorithms, the beauty of them is not
    in that the methods call themselves. It is that the methods make use of previous results that were stored
    on the stack.

    Regards,
    Jim
    Last edited by jim829; 09-11-2014 at 04:12 AM. Reason: grammar
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  8. #8
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,143
    Rep Power
    14

    Default Re: Simple Recursion

    Are you going to do my homework for me next?

    Note: spoonfeeding is NOT helping. Here's why: The Problem with Spoon-feeding
    How to Ask Questions the Smart Way
    Static Void Games - GameDev tutorials, free Java and JavaScript hosting!
    Static Void Games forum - Come say hello!

  9. #9
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    5,114
    Rep Power
    12

    Default Re: Simple Recursion

    Well... it is if you are spoon-feeding an infant.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  10. #10
    nellac77 is offline Member
    Join Date
    Sep 2014
    Posts
    2
    Rep Power
    0

    Default Re: Simple Recursion

    Thanks for the help. I would have liked the walk-through on the recursion sans the solution to my assignment, but that's my fault from the original post. I am checking out codingbat.com right now, and its actually pretty cool. Thanks again!
    gimbal2 likes this.

  11. #11
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Simple Recursion

    Quote Originally Posted by nellac77 View Post
    Thanks for the help. I would have liked the walk-through on the recursion sans the solution to my assignment, but that's my fault from the original post.
    No it's not. You provided a snippet of your code and simply asked for advice not a solution. Nothing at all wrong with that.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Simple Recursion

    Quote Originally Posted by jim829 View Post
    No it's not. You provided a snippet of your code and simply asked for advice not a solution. Nothing at all wrong with that.
    Oh yes, a lot was wrong; the OP said 'it'; proof;

    Quote Originally Posted by the OP
    I have started with:
    *shudder*

    kindest regards,

    Jos (Ni! Ni!)
    Build a wall around Donald Trump; I'll pay for it.

  13. #13
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Simple Recursion

    Well, I fail to see how that is asking for code. The OP started with some code. It didn't do what the OP wanted. So that OP asked
    for advice. Asking for advice is not, imho, asking for code.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Simple Recursion

    Quote Originally Posted by jim829 View Post
    Well, I fail to see how that is asking for code. The OP started with some code. It didn't do what the OP wanted. So that OP asked
    for advice. Asking for advice is not, imho, asking for code.
    Of course the OP wasn't asking for code; I was only fooling around; it's Friday afternoon overhere.

    kind regards,

    Jos (<-- has to explain everything; always; to anyone ;-)
    Build a wall around Donald Trump; I'll pay for it.

  15. #15
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    5,114
    Rep Power
    12

    Default Re: Simple Recursion

    Quote Originally Posted by JosAH View Post
    it's Friday afternoon overhere.
    Ni!

    Of course you have to explain everything to everyone; you're the supreme chancellor after all.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

Similar Threads

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  2. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 01:13 AM
  3. Recursion help
    By rjg_2186 in forum New To Java
    Replies: 1
    Last Post: 01-02-2009, 08:03 AM
  4. help with recursion
    By Nari in forum New To Java
    Replies: 15
    Last Post: 04-24-2008, 09:13 AM

Tags for this Thread

Posting Permissions

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