my dog learned polymorphism*
The moose likes Beginning Java and the fly likes Recursive Method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursive Method" Watch "Recursive Method" New topic
Author

Recursive Method

tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
Hi, I made the following method to look for a String within a given text file:



My question is.. how can I substitute the while loop for a recursion ?
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
Why do you want to create a recursive method here? Although you can in general replace loops with recursive methods, I don't think it is required in this particular case.
tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
I'm required to in my assignment. I made this method to verify that i could do it using iteration.. but I'm required to do it recursively using linenumberreader.. can someone help me out please?
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
Sure, but I doubt anyone would hand out the solution to you directly. Do tell us how much you've progressed.
tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
Well i can't really think of anything.. I know I might have to use an if/else statement .. I guess I would use

if ( line contains key)
{
return info..
}

else{

read next line...
call method again...
}

this results in a Stack Overflow error though.. and I don't really know how to get the method to read the next line and start from there after the recursion...

but that's really all I can think of I"m rather new to recursion..
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
Okay, lets then have a basic understanding of what a recursive method is comprised of.

a) A method that takes as input, a recursively changing parameter for each call. (In our case, the contents of current line)

b) A simple check on the content of that changing parameter. If it is a favourable result, we either move forward in the recursion or we return a valid result, if not exit and return out of the method.

Here in our case, there are 2 checks ->

i) if line data is null, do no more and return null.
ii) if line data contains key, we return with the line data.

c) If none of the checks pass, call the recursive method again with the changed argument. In our case, call the same method with next line data(through readline method)
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
tom [surl='http://jenkins-ci.org/' class='api' title='Continuous Integration Engine wrote:jenkins[/surl]]

this results in a Stack Overflow error though.. and I don't really know how to get the method to read the next line and start from there after the recursion...

but that's really all I can think of I"m rather new to recursion..


Please do post your actual code, we can work on that.
tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
this was what i came up with, a shot in the dark, but maybe I'm close? needless to say i only got a null returned..

Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
tom jenkin wrote:


Okay, first of all, searchFile should not be a recursive method. As you can see from its parameters, key and File are constants and do not change on each call, instead you should be looking to extract just the while loop part into recursion.

See this,

tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
Thanks for the help so far I have this..



I tested the code out.. so far it works except that when it finds the String i'm looking for it keeps going and because of that I'm getting a null returned instead of my key (which it did find but it is overwritten) .. how can i stop the recursion after it finds it??
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8244
    
  23

tom [surl='http://jenkins-ci.org/' class='api' title='Continuous Integration Engine wrote:jenkins[/surl]]this results in a Stack Overflow error though...

Which doesn't necessarily mean that the method is wrong (and actually, your pseudo-code looks almost right).

The problem with recursive methods is that there's a limit to the number of times you can call them, and you will get a StackOverflowError if you exceed it; which is why you generally only use recursion when there is a distinct advantage for it. Think of it as the JVM telling you: "you've called this method too many times, chum".

Big hint: Since the LineNumberReader is the thing that changes when you read a new line, I'd consider passing 'lnr' as a parameter; however, as I said above, even if you get the method right, it still may not stop the error; and that's because, as others have said, you really don't need recursion for what you're doing.

And your problem right now is that you don't know whether you're getting the error because the logic is wrong, or because the file is too big. I would expect to be able to read a few hundred lines before running into stack depth problems, so if your file is much shorter than that I would suspect the former; but it's just a guess.

My suggestion: add some System.out.println() statements so that you can see what the method is doing on each call. That's the surest way to check if it's doing what you want.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39869
    
  28
Praveen Kumar M K wrote:Why do you want to create a recursive method here? Although you can in general replace loops with recursive methods, I don't think it is required in this particular case.
Actually, if you study the program semantics, loops and recursion are indistinguishable in their semantics.

But I agree a loop is a much better way to code this particular problem.
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
tom [surl='http://jenkins-ci.org/' class='api' title='Continuous Integration Engine wrote:jenkins[/surl]]Thanks for the help so far I have this..



I tested the code out.. so far it works except that when it finds the String i'm looking for it keeps going and because of that I'm getting a null returned instead of my key (which it did find but it is overwritten) .. how can i stop the recursion after it finds it??


Great! You just need to return the result from the recursive method call(line 28). Let us know if that works.
Praveen Kumar M K
Ranch Hand

Joined: Jul 03, 2011
Posts: 256
Campbell Ritchie wrote:
Praveen Kumar M K wrote:Why do you want to create a recursive method here? Although you can in general replace loops with recursive methods, I don't think it is required in this particular case.
Actually, if you study the program semantics, loops and recursion are indistinguishable in their semantics.

But I agree a loop is a much better way to code this particular problem.


I've always "believed" that recursion should be used in problems where you can reduce the number of iterations(by any degree). For example, a binary search crunches the search by half every time. Likewise finding a node inside a xml DOM tree.
tom jenkins
Greenhorn

Joined: Apr 18, 2012
Posts: 27
I think I got it working now, thanks a lot! thought it stops at the first line of the key it finds and terminates.. how can I modify it to return more than one line if there is more than one match in the file??



Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

tom [surl='http://jenkins-ci.org/' class='api' title='Continuous Integration Engine wrote:jenkins[/surl]]how can I modify it to return more than one line if there is more than one match in the file??


You'll need to return a Collection or array of lines, possible wrapped in a class (if there's other information that it makes sense to bundle up with it). A List seems like the most likely candidate, barring further requirements.
 
jQuery in Action, 2nd edition
 
subject: Recursive Method