Recursion

Recursion

Post by Jonatha » Thu, 27 Nov 2008 07:23:03


I am having some problems trying to get the following code to work.
If anyone could give me some help with it, I would greatly appreciate
it.

I know recursion is usually a terrible method but I am required to use
it for my exercise. I have to be able to read the lines from a file
and output them in reverse order onto another file. So the infile.txt
has the lines
hello,
how are you,
i am fine,
thats great.

and the outfile must look like this
thats great.
I am fine,
how are you,
hello,

So I have the infile and outfile working correctly I am just having a
problem with reversing the lines using recursion. The following is my
code.

import java.io.*;

public class Ex9a {
private static BufferedReader br;
private static PrintStream ps;

public static void main(String[] args) throws IOException{
File f = new File("infile.txt");
File g= new File("outfile.txt");
FileInputStream fis;
FileOutputStream fos;
InputStreamReader isr;


String read;

if (f.exists()){
fis = new FileInputStream(f);
isr = new InputStreamReader(fis);
br = new BufferedReader(isr);
fos = new FileOutputStream(g);
ps = new PrintStream(fos);


while((read=br.readLine())!=null){
Ex9a.reverse(read)


br.close();
}
}else
System.out.println("File I/O error");



}
//Following is Method for reversing the lines
public static String reverse(String rev)throws IOException{
//this is where i am stuck
String s = br.readLine();

if(rev == null){
return rev;

}else{
return rev;

}

}

}

Again any help would be appreciated
 
 
 

Recursion

Post by Mark Spac » Thu, 27 Nov 2008 07:49:29


I don't see how you can print the last line first, until you read the
last line. Here you read the first line, then immediately try to
reverse it. Not gonna work.

Read in everything first (hint: have you covered arrays yet? ArrayList?).

Then reverse the whole array, not just the first line.

Also, try not to close the input file in the read loop.

 
 
 

Recursion

Post by rossu » Thu, 27 Nov 2008 08:37:57

On Tue, 25 Nov 2008 14:23:03 -0800 (PST), Jonathan



[snip]

You are doing the same thing in both branches of the if statement.
Why?
Where are you recursing? Recursion involves a method calling itself:

int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-2) + fibonacci(n-1); // Recursion here
}
}

Horribly inefficient, but it demonstrates that you need to call the
function within itself.

Since you want a way to reverse the order of the lines, think of a
non-recursive way to reverse the lines using a stack. Now think how
you can use the call stack to do the same thing by recursing.

rossum
 
 
 

Recursion

Post by Lew » Thu, 27 Nov 2008 10:38:21


The point of recursion is that a method calls itself. To work properly, there
need to be two parts to the method - one part is the stop condition, which
ends the recursion, and the other part is the continue condition, which
invokes the method itself recursively. Think of when the recursive method has
to stop - code that part first. Then code the other part, thinking of what
work the recursed call has to do, what work the non-recursed code has to do,
and in which order the recursed and non-recursed code has to execute.

Here's one approach, completely untested, not even compiled, and not by any
means the only way:

public void reverse( BufferedReader in, BufferedWriter out )
throws IOException
{
String line = in.readLine();
if ( line != null )
{
reverse( in, out );
out.write( line );
out.newLine();
}
}

Don't forget to flush.

Your thought to use String is entirely valid. Just think carefully about how
you'd put lines into a String in backwards order. rossum's advice to think of
how you'd do it in a loop might help. Recursive and looped algorithms both
involve repeating a part of the action.

Get out of the habit of writing everything as static methods.

--
Lew
 
 
 

Recursion

Post by Jonatha » Thu, 27 Nov 2008 10:55:35


> public void reverse( BufferedReader in, BufferedWriter out ) >> hrows IOException> > >
> tring line = in.readLine(>;
> f ( line != nul> )
> >
> everse( in, >ut );
> ut.write(>line );
> ut.>ewLine>);
>>>}
> }
>
> Don't forg>t >o flush.
>
> Your thought to use String is entirely valid. ust think careful>y about how
> you'd put lines into a String in backwards order. ossum's advice>to think of
> how you'd do it in a loop might help. ecursive and looped alg>rithms both
> involve repeating a part of>th> action.
>
> Get out of the habit of writing everything as sta>ic>metho>s.
>
> --
> Lew

Thanks for the help everyone. I'll give this exercise another try
tonight and see how it goes.
 
 
 

Recursion

Post by Tony Dahlm » Sun, 30 Nov 2008 14:17:32


Recursion, when you are comfortable using it, can become a useful
strategy in your arsenal. Your professor wants you to get comfortable
using recursion, but has thrown in file I/O, exception catching, etc.
just to make sure you are getting familiar with the Java libraries and
language.

To what Lew and rossum have said, I would only add that your recursive
methods should return void.

Example:
public class CountTo20 {
private int count = 0;

private void countTo20() {
int myCount = count++;
if( count <= 20 ) {
// countTo20();
System.out.println(myCount + 1);
countTo20();
}
}

public static void main(String[] args) {
new CountTo20().countTo20();
}
}
So, this code counts to 20, printing the series of numbers, right?
And what happens if you move the recursive countTo20() method before
the call to println()?

Get it? Regards, Tony Dahlman
 
 
 

Recursion

Post by Lew » Mon, 01 Dec 2008 03:23:39


Not necessarily.

It is quite common for recursive methods to return a value.

--
Lew
 
 
 

Recursion

Post by Tony Dahlm » Mon, 01 Dec 2008 10:52:53


Thanks, Lew. I read that misinformation somewhere and just accepted
it on faith. So now I realize this will print every other number
from 1 to 20, backwards of course. :-)

public class CountTo20 {
private int count = 0;

private boolean countTo20() {
int myCount = count++;
boolean toggle = false;
if( count <= 20 ) {
toggle = countTo20();
if( toggle )
System.out.println(myCount + 1);
}
return !toggle;
}

public static void main(String[] args) {
new CountTo20().countTo20();
}
}

That's really cool! - Tony
 
 
 

Recursion

Post by Lew » Wed, 03 Dec 2008 06:56:37


> private int count = 0;> >> > private boolean countTo20()>{
> nt myCount = cou>t++;
> oolean toggle > false;
> lt;f( coun> <= 20 ) {
> toggl> = countTo20();
> gt;if( toggle )
> yste>.out.pri>tln(myCount + 1);
> gt;> >>eturn !toggle;
> }
>
> pub>ic static void main(String[] args) >
> > gt;ew>Co>ntTo20().countTo20();
> }
>
> }
>
> That's really cool! Tony

Consider following the Usenet standard (I forget the RFC number) of
setting off sigs from the body of the post with a single line of "--
" (dash dash space).

Another very useful recursive idiom, well-known to functional-language
programmers (LISP, Prolog), is to pass an intermediate result to a
recursive helper method.

Untried:

public long factorial( int n )
{
return factorialHelper( 1, n );
}

public long factorialHelper( long total, int n )
{
return ( n == 0? total
: factorialHelper( n * total, n - 1 ));
}

This particular example is tail-recursive, and thus relatively easy to
refactor as a non-recursive loop algorithm.

Lew