Win a copy of Murach's Java Programming this week in the Beginning Java forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Java recursion method find largest  RSS feed

 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wrote below code to find largest number in an array. First it sends in array second position its starting to check the array from.

If array only has one element code runs properly, showing first element as largest. If there are more elements like 6 of them then I get the below error. Why?

23rd line is compare = largestRec(arr,pos++);



 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What does your very first call to this method look like? Is the second argument you pass the length of the array?
 
Paul Clapham
Sheriff
Posts: 22268
38
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your problem occurs because you used "pos++" instead of "++pos".
 
Liutauras Vilda
Marshal
Posts: 4262
256
BSD
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:Your problem occurs because you used "pos++" instead of "++pos".

@OP
1. Now you may wonder why? That is because 'pos++' is post-increment operator, that means you're passing current 'pos' value as an argument and then increment it. Since you have recursion here, your incremented value gets lost in the bermuda recursion, hence, you always pass the same value, which is probably the one you had initially assigned.

2. However, did you get instruction, that array can contain only natural numbers? Such assumption you make in your code, line 5. If your assumption appears to be wrong, look for Integer class in Java API, there you should be able to find a value which would get you out of this limitation.

3. Method name. I think you could come up with a better name. Now look at the comment above method name - you'll catch yourself that you had a need to explain what this method is supposed to be doing. This is the first sign, that method name is either non-descriptive or in the worst case - misleading. Think towards: findLargestNumber or similar along this line.

4. Formatting. Or more precise, braces placing style. Look what style uses method:
Now look what style uses if/else statement
In short - your style is inconsistent. You randomly choose the style and apply unpredictably. Better would be to choose one and follow it, unless you're forced to use specific one, but again, it should be same style across all code.

5. Two possible errors here. [1] Try not to omit braces even if there is one statement only. You won't notice when you slip on that otherwise. [2] after the 'if' there should be a space. No space when methodName(parameters).

6. Inconsistencies. Notice? [1] case. Space between different parameters (preferred). [2] case. No space.

7. And finally. I find confusing variable name 'compare'. Might it just me, but it doesn't fit to the exercise borders to me.

As you see, those are quite small details, but they all count to the beauty of your code. Always have a such goal set for yourself, that your professor or anybody else looking to your code could say - "An exemplary work!".
 
Campbell Ritchie
Marshal
Posts: 54893
155
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:. . . those are quite small details . . .
If you come back to that code late in the Summer and have forgotten what it is supposed to do, then bad variable names will make the code much more difficult to understand. It will have become quite a large detail in six months.
 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am not suppose to touch any code in this whole class except the code I posted this page. So many approaches including Math.max won't work because I am not suppose to import anything.

Junilu Lacar wrote:What does your very first call to this method look like? Is the second argument you pass the length of the array?


First argument is array, second argument is the position it starts to check the largest. In example, array has 8 elements and code checks from 3rd element to 8th element the largest. 3rd would be position. It's hard coded to send in 0 but we assume it's not.




Paul Clapham wrote:Your problem occurs because you used "pos++" instead of "++pos".


Well good catch, I changed that and now it runs but only 2 cases true, the rest false.




@Liutauras Vilda: I read your whole comment and took notes on a side from it. Very helpful thank you! I do totally agree organization and sleek coding helps whole lot!
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your poor choice of names, especially with the variable you called compare, is what's preventing you from seeing the problem.  The value you assign to the variable max on line 5 is the problem with your implementation.  Another problem I see is the expression you use on line 9. While not technically incorrect, it doesn't help clarify the logic.  The expression arr[pos] is a formula and it doesn't clearly express what value it represents.  This line is actually related to what you'd be expressing on line 5 if you change it to assign the correct value to max.

If you try to talk (out loud) your way through the algorithm and explain it to someone or yourself, without saying things like "arr pos" or "pos equals arr length minus one" but instead explain what these mean, then you can figure it out.
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:I find confusing variable name 'compare'. Might it just me...

See, Liutauras pointed out the same problem with the variable compare. It doesn't fit, therefore it misleads the reader and obscures the flaw in the logic.
 
Fred Kleinschmidt
Bartender
Posts: 544
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is the assignment to write a method to find the largest element, or is it to write a recursive method to find the largest element? in other words, is it required to write a recursive method? The reason I ask is that a recursive method is probably the least efficient and most verbose way to do this, and is the way I would ever try.
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you still find yourself struggling to figure out a better name for that compare variable, focus on this line of code:

This line could be much more expressive than it is now. All the names are not well chosen; they all obscure the intent by revealing their implementation instead.  The name arr is meaningless in terms of intent but it sure says a lot about its implementation, that it's an array. So what? The name pos is not much better. Ok, so it's a position. Again, so what? The name largestRec hints at the recursive nature of the method, an implementation detail, with the suffix "Rec". Again, so what?  We already pointed out how the name compare is a bad name, but it hints at the fact that it's going to be compared to something else later on. Once again, so what? None of this explains what you're trying to do.

If I could make an analogy, this one line of code is like somebody walking around with a screwdriver, a drill, and some wire, and explaining what he's doing like this: "Well, I'm going to drill a hole in the wall with this drill. Then I'm going to use this screwdriver to drive a screw into the hole. Then I'm going to loop this wire around the head of the screw." All implementation details.

This is what the guy should have said so that his intent was clear: "I want to hang a picture on this wall over here."

Do you see the difference?
 
Carey Brown
Bartender
Posts: 2703
41
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:


Your answer will always be the last number in the array.

You have

in your method. In each nested call a new 'max' is created and initialized to -1. They way you have it written the int returned from the method will always be > -1 and set max which is then returned. For max to work properly you have to compare  two array elements not one array element against -1.
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One last clue and I'll stop pestering you...

Without even seeing the actual code you ran that gave the last batch of tests results you posted, I'm going to predict these outcomes:
 
Liutauras Vilda
Marshal
Posts: 4262
256
BSD
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:So many approaches including Math.max won't work because I am not suppose to import anything.
Math.max is part of java.lang package, that means it is imported automatically without asking your or your teacher's permission. Anyway, while Math.max could have its use here, I don't think it is crucial.

Having said that, can you give us exact requirements? So we wouldn't give you hints which aren't permitted based on the given instructions.
 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:
Recaip Sanli wrote:So many approaches including Math.max won't work because I am not suppose to import anything.
Math.max is part of java.lang package, that means it is imported automatically without asking your or your teacher's permission. Anyway, while Math.max could have its use here, I don't think it is crucial.

Having said that, can you give us exact requirements? So we wouldn't give you hints which aren't permitted based on the given instructions.


Requirement says this:
In the RecursiveMethods class, you are required to implement the following methods using
recursive solutions (no looping statements):
largestRec(int[] arr, int pos) – This method takes an integer array as well as an
integer (the starting index) and returns the largest number in the array.


I corrected below some of the names to the best instance names I can come up with, code still won't run..



Error
 
Carey Brown
Bartender
Posts: 2703
41
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
'max' was declared local to your if() block and is not visible to the return. Two choices: declare max outside of the block, or, inside the block just return whichever is greater.
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:
Requirement says this:
In the RecursiveMethods class, you are required to implement the following methods using recursive solutions (no looping statements):
largestRec(int[] arr, int pos) – This method takes an integer array as well as an integer (the starting index) and returns the largest number in the array.

( ლ.<) -- sheesh

No wonder you're not choosing good names. Frankly, those names are cr*p.

Ok, so that's what you have to submit but nobody is forcing you to work with them in the meantime. I suggest that you use good, sane names anyway while you develop the solution. This way, you can get a better understand of exactly what's happening in your program.

If you can't reconcile what you're thinking with the code that you're writing, then your program will most likely be incorrect. If your understanding of the problem and solution is incomplete and unclear, then unclear and misleading code will not help you find where there are gaps in your logic. Only clear code that helps you understand what it's doing will help you figure out what needs to be changed so that the program will behave the way you think it should behave.

Here, I'll give you a gift of some decent names to work with. If your instructor insists that you submit code that uses those bad names he/she provided, so be it, change these good working names back to the bad names your instructor is expecting you to use in your submissions, but only change them back after you get your program working correctly with these good names.

If this were me, I'd first refactor the method largestRec(int[] arr, int pos) and rename things so I can work with something like this:

When I read that code out loud, it will sound like I'm just explaining the algorithm:

"I want to search for the maximum value of a given array of numbers, starting from a specific index.  If I'm starting from the last position of the array, that means this is the only number left to look at and therefore, it must be the largest one for this execution of the method. So, I will ... "  -- You can take the "story" from here and try to finish it.

If you look at the code and compare it to what I bolded in the above description of INTENT, you'll see a strong correlation between them. This is what's called *coherence*.

 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know if you noticed this but the code that I gave above is essentially the same code you had. The only difference are in the names I used. Those names reveal the intent of the code much more clearly than the bad names you were told to use.  The names I gave you help tell the story of the code, not the mechanics/implementation.
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And if I really wanted to make sure my code was clear and read out loud like plain English, I'd refactor from this:

to this:

There are many programmers who will object to a refactoring like the above, complaining that it will make the program inefficient and slow. To that I'd say, "Rubbish!"

An optimizing compiler will most likely inline those statements anyway. Besides, I don't optimize by intuition and gut feel. Show me compelling evidence of a significantly large slowdown in performance and the conditions under which that slowdown will occur and I'll show you a situation that is most likely NOT ever going to be relevant to this code. Clarity, however, is of utmost importance if you're going to make the code behave correctly. So there. :-Þ
 
Paul Clapham
Sheriff
Posts: 22268
38
Eclipse IDE Firefox Browser MySQL Database
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:
Paul Clapham wrote:Your problem occurs because you used "pos++" instead of "++pos".


Well good catch, I changed that and now it runs but only 2 cases true, the rest false.


My personal practice is to never use either x++ or ++x except in the well-known idiom "for (int i=0; i<something; i++)". It's just too much trouble to bother remembering which does pre-increment and which does post-increment, especially since "x = x+1" is easier to understand anyway.>
 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:My personal practice is to never use either x++ or ++x except in the well-known idiom "for (int i=0; i<something; i++)". It's just too much trouble to bother remembering which does pre-increment and which does post-increment, especially since "x = x+1" is easier to understand anyway.>

In this program, pos+1 also makes more sense semantically. There's a subtle but significant difference between ++pos and pos+1. The pre-increment has a side effect of changing the value of the parameter. This doesn't happen when you just add 1 using the + operator. There's no reason to change the value of the parameter within the method and using the incremented parameter value later on in the code would actually be either a mistake or a pointless flourish.
 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I do appreciate all feedbacks. They all talk about important points. You guys are obviously much more knowledged in Java than me, my hopes were either getting some ideology or code excerpt at the least so it is helpful to move towards coming up with a solution. Besides what I wrote down I am pretty much stuck here. Besides the point of the naming, indenting and other important parts of the code. I must get it working, doing what I want it to do. I recently learned debugger of jGRASP, played with that on this code, still no help. Totally lost.

Below are all files I have at the point. It's due tomorrow and I can put the answer this weekend if anyone wants to see. If anyone wants to give it a shot for themselves, go ahead.

RecursiveMethods


TestRecursiveMethods


LNode
 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rules are here:

In the RecursiveMethods class, you are required to implement the following methods using recursive solutions (no looping statements):

largestRec(int[] arr, int pos) – This method takes an integer array as well as an integer (the starting index) and returns the largest number in the array.

sumRec(int[] arr, int pos) – This method takes an integer array as well as an integer (the starting index) and returns the sum of the values in the array.

reverseStringRec(String s) – This method reads a string and returns the string in the reversed order.

The following method is for bonus points so its implementation is not mandatory:
reverseListRec(LNode head) – This method takes a reference to the head of a linked list and returns the reference to the head of the linked list in the reversed order.
Note that you are only supposed to touch the above four methods. You are NOT allowed to create any other methods, instance variables, or make any changes to methods other
than these four methods or files other than "RecursiveMethods.java". You should also NOT change the content of the array that is passed into each method. Points will be taken off if you fail to follow this rule.
 
Recaip Sanli
Ranch Hand
Posts: 69
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good news, I came up with super compact answer working on improving a snippet I found.

Thank you for everyone! I truly appreciate every single try and input. I do agree with many of you on writing future in mind and ease of understanding later on!



Test Driver



 
Junilu Lacar
Sheriff
Posts: 10929
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That test driver class: and (ლ.<) ...(sheesh)

I guess whoever wrote that never heard of extracting to a method to eliminate duplication or JUnit for unit testing

Good job finding a solution but as we mentioned, it's preferable to use pos+1 instead of ++pos because there is no need to change the value of pos, which is what the pre-increment operator does.
 
Paul Clapham
Sheriff
Posts: 22268
38
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just one annoying little thing: That beautiful recursive code will fail if it's given an empty array.
 
Liutauras Vilda
Marshal
Posts: 4262
256
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just double check with your instructor you are finally allowed to use that Math.max()
Recaip Sanli wrote:So many approaches including Math.max won't work because I am not suppose to import anything.

Recaip Sanli wrote:Good news, I came up with super compact answer
 
Paul Clapham
Sheriff
Posts: 22268
38
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:Just double check with your instructor you are finally allowed to use that Math.max()
Recaip Sanli wrote:So many approaches including Math.max won't work because I am not suppose to import anything.


Well... the Math class is in the java.lang package, which is automatically recognized by the compile without having to be imported. So you don't have to write "import java.lang.Math". Whether that means you aren't importing anything or whether the compiler's ability to know about the java.lang package without import statements means it's automatically importing all of java.lang, and in that case whether that means you are actually importing java.lang.Math just by using it, I don't know.
 
Frits Walraven
Creator of Enthuware JWS+ V6
Bartender
Posts: 2946
208
Android Chrome Eclipse IDE
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Congratulations Recaip Sanli   your question has made it to our CodeRanch Journal - February 2017

Have a Cow!
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!