# Thread: Simple Recursion

1. Member
Join Date
Sep 2014
Posts
2
Rep Power
0

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

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

4. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
13

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

6. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
13

## Re: Simple Recursion

Originally Posted by AlexGraal
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

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

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

## Re: Simple Recursion

Well... it is if you are spoon-feeding an infant.

10. Member
Join Date
Sep 2014
Posts
2
Rep Power
0

## 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!

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

## Re: Simple Recursion

Originally Posted by nellac77
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

12. ## Re: Simple Recursion

Originally Posted by jim829
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;

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

kindest regards,

Jos (Ni! Ni!)

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

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

14. ## Re: Simple Recursion

Originally Posted by jim829
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 ;-)

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

## Re: Simple Recursion

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

Of course you have to explain everything to everyone; you're the supreme chancellor after all.

#### Posting Permissions

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