• Post Reply Bookmark Topic Watch Topic
  • New Topic

Listing Files and Directories and Files of those Directories recursively  RSS feed

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I'm trying to find a means of listing files and directories in a directory, and files within those subdirectories recursively. In the recursive method that I'm working on, for a base case, I assume it is when the root directory has no sub-directories. However, using the file class, to check if there are no sub directories in a directory, I can't think of how to do that without using iteration (for loop).

This is what I have so far, but I'm genuinely stuck, because this method can only use recursion:



thanks!
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37507
552
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What if the base was "this file is not a directory"? Then you recurse one level lower than now, but don't need a loop.
 
Paul Clapham
Sheriff
Posts: 22835
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So you want to find out whether there are files in a directory? Well, let's take the case where there are (say) 23 entries returned by the File.listFiles() method. Now, some of those 23 entries may be directories and some may be files, i.e. not directories. I can't think of a way to find out whether any of them are files without looking at each of the 23 entries. I'm not sure why you want to avoid the loop, anyway.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursive list processing without loops is very common in functional programming. Basically, you keep slicing the list into two parts: the head element and the rest of the list, aka the tail. You process the head and then keep recursing with the tail until the next tail is empty.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jeanne Boyarsky wrote:What if the base was "this file is not a directory"? Then you recurse one level lower than now, but don't need a loop.


That sounds interesting, but I'm not too sure if I understand. By recursing one level lower, if the file is not a directory, but a file, it would just return the fileSize of the file. However, how can I determine exactly what the base case should be?
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:So you want to find out whether there are files in a directory? Well, let's take the case where there are (say) 23 entries returned by the File.listFiles() method. Now, some of those 23 entries may be directories and some may be files, i.e. not directories. I can't think of a way to find out whether any of them are files without looking at each of the 23 entries. I'm not sure why you want to avoid the loop, anyway.


The reason I'm trying to avoid a loop is because I'm supposed to find a means to do this completely recursively. It definitely makes the problem a lot tougher for me as iteration just naturally seems easier than building a recursive stack.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:Recursive list processing without loops is very common in functional programming. Basically, you keep slicing the list into two parts: the head element and the rest of the list, aka the tail. You process the head and then keep recursing with the tail until the next tail is empty.

Usually a recursive method to visit all files in a tree incorporates a loop somewhere in the method. Although you could, as you say, recursively slice a list into parts, that won't work when the only parameter you're given is a File, not a List.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:Usually a recursive method to visit all files in a tree incorporates a loop somewhere in the method. Although you could, as you say, recursively slice a list into parts, that won't work when the only parameter you're given is a File, not a List.

If the only parameter you are given is a file, how do you propose to loop through it?
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Carey Brown wrote:Usually a recursive method to visit all files in a tree incorporates a loop somewhere in the method. Although you could, as you say, recursively slice a list into parts, that won't work when the only parameter you're given is a File, not a List.

If the only parameter you are given is a file, how do you propose to loop through it?



P.S. I said 'File', with an upper case.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So if the file is a directory, you get a *list* of files in it... Now you're back to splitting the list into two parts and recursing without a loop
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:So if the file is a directory, you get a *list* of files in it... Now you're back to splitting the list into two parts and recursing without a loop

Ok, so you split the list in two, how do you propose to pass each list back to your recursive method that only takes a File?
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:So if the file is a directory, you get a *list* of files in it... Now you're back to splitting the list into two parts and recursing without a loop

Maybe it would help if we saw your pseudo code.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Learning Scala from Martin Odersky on coursera.org  was a little mind-blowing because of all the x:xs and recursion he did without the use of loop iteration. It opened my mind to a whole 'nother world of possibilities though. If you've solved these kinds of problems forever using loops, making that mental leap to abandon them in favor of tail recursion and list splitting is pretty mind-bending. I kid you not, I could almost literally feel my mind bending...

You can easily work out the algorithm if force yourself to forget about for loops and just think list[0] and list[1:] are the only things you need. The base case is when the file is not a directory, which means you just print the name and the current line of recursion stops.If the file is a directory, the you very a list of Files under it and start recursing into that, starting with the first file, then recurse with the tail.

In Scala, if I remember correctly, you had a type switch. In Java, you'll probably have overloaded methods, on that takes a File, the other that takes a List<File>.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not saying that visiting each file couldn't be done without a loop but you'd need a different method signature in order to do it.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On second thought, scratch the idea of two methods. You just need a method that takes List<File>. Base case is when list.size() is 0 or 1 and the File, if there is one, is not a directory.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:On second thought, scratch the idea of two methods. You just need a method that takes List<File>. Base case is when list.size() is 0 or 1 and the File, if there is one, is not a directory.

Ah, now we're on the same page. 
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A thought... if the signature was

then it could be called either with a single File as the OP had but also with an array, along the lines you suggest.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that's an excellent thought, Carey. I wish I'd had it first but since you did, you get a cow

In fact, that idea makes we want to try to write this in Go now because it has some nice operations with slices and variatic parameters 
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks, that was fun.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is quite the complex problem lol
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's a bit of a puzzler, yes, but everything you need to come up with less than 25 lines of code for a method that solves the problem can be inferred from the discussion above. I bet I can do one with fewer than 20 lines, 15 even if using a different code formatting style.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu, yes, it is a bit of a puzzler. The problem now is that I get my method to do a bit of recursion, but I don't actually think it's recursing. Essentially, what's happening as I trace my method, what's happening is that the method takes the last file and adds it to the file at index[0] to get the total size of the directory.  Am I not checking for something? My method doesn't seem to be a tail recursive method, please have another look.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A couple of questions:
1. What is the significance of the long return value?
2. Is the parameter list constraint to what you have?

The first question has to do with intent. What is the returned value supposed to represent?

The second question pertains to Carey's reply where he shows a slightly different method signature. I don't see any way for you to arrive at a correct solution with just a File parameter like what you have now.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru, I think you need to take a step back from the problem. What if you were asked to print an array of Strings using recursion instead of a loop?
If you have followed the earlier posts you'd see that this only works with variable length arguments, as in String... strings. The reason that this is necessary is that the recursive algorithm depends on the ability to operate on an array. Line 6 is already an array so it wouldn't have been an issue. Line 3 however is not written as an array, BUT, thanks to the miracle of variable length arguments, the compiler turns it into an array on our behalf. On line 10 strings is passed to the body of the method as a String[] array.

Line 18 uses copyOfRange() to generate a new array without the first entry, thereby reducing the length of the array by one.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:A couple of questions:
1. What is the significance of the long return value?
2. Is the parameter list constraint to what you have?

The first question has to do with intent. What is the returned value supposed to represent?

The second question pertains to Carey's reply where he shows a slightly different method signature. I don't see any way for you to arrive at a correct solution with just a File parameter like what you have now.


The long value returns the length of the directory/files in the directory. Essentially, what it does is that it recursively enumerates the directory and returns a value corresponding to the size (length) of the entire directory. The parameter list is constraint to what I have sadly. However, there are other methods in other classes and within this class itself that supplement this method.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If variable length parameters are confusing you could provide an additional overloaded helper method that prepares the single parameter by converting it into an array before calling the recursive method which is designed to take an array.

This is the long hand approach to what the compiler and variable length parameters would have done for you automatically.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:Naziru, I think you need to take a step back from the problem. What if you were asked to print an array of Strings using recursion instead of a loop?
If you have followed the earlier posts you'd see that this only works with variable length arguments, as in String... strings. The reason that this is necessary is that the recursive algorithm depends on the ability to operate on an array. Line 6 is already an array so it wouldn't have been an issue. Line 3 however is not written as an array, BUT, thanks to the miracle of variable length arguments, the compiler turns it into an array on our behalf. On line 10 strings is passed to the body of the method as a String[] array.

Line 18 uses copyOfRange() to generate a new array without the first entry, thereby reducing the length of the array by one.


Hello Carey, you may be right, but unfortunately, I'll give what you said a try and report back to you. Thanks Carey!
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This problem is tricky if you adhere to the requirements as you've stated, which is why I suspect that you may have interpreted the instructions incorrectly. The typical implementation is recursive but does contain a single loop.

 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey, I hope that it's ok for me to send you a quick PM. just to verify with you that I'm interpreting what I'm reading correctly.
 
Carey Brown
Saloon Keeper
Posts: 3328
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Naziru, I've read through the requirements that you PM'd me and I do think you've misread the instructions. They were talking about using a loop for the tree depth which is different than using a loop to go through all the children at a given position. This makes the problem much simpler. See my last post.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:Naziru, I've read through the requirements that you PM'd me and I do think you've misread the instructions. They were talking about using a loop for the tree depth which is different than using a loop to go through all the children at a given position. This makes the problem much simpler. See my last post.


Got it, will do Carey! Thanks!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!