aspose file tools*
The moose likes Beginning Java and the fly likes Recursive algorithm doubt Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursive algorithm doubt" Watch "Recursive algorithm doubt" New topic
Author

Recursive algorithm doubt

Anirvan Majumdar
Ranch Hand

Joined: Feb 22, 2005
Posts: 261
I had come across the following code snippet :



The above mentioned method is supposed to recursively call itself and segregate between directories and files for the dir. path passed to it as an argument. My problem is not with the code snippet (it works perfectly fine), it is with the algorithm. As you can see, the File[] dirs, is recursively loaded with any subsequent directory structure found inside the starting directory.
What i can't quite figure out is, once the directory structure of a sub-directory is loaded into File[] dirs, how can it still hold on to the earlier directory elements?

For eg. let assume there's Directory A which consists of sub-dir.B,C,D.
So in the first loop File[] dirs = {dir.B, dir.C, dir.D}
In the second loop, File[] dirs = {contents of dir.B}.
So, after parsing through the contents of dir.B how does the contents of File[] dirs get loaded with the contents of dir.C and after that dir.D. Basically, how does the File[] hold onto the initial values???
Seb Mathe
Ranch Hand

Joined: Sep 28, 2005
Posts: 225
I think you're taking a wrong way...

As you say, the "enty point" of your search is a directory (named A), would'nt it be better to change your method signature to "search(File root)" and having something like that ?



It's a common way to display a tree of files, for example...
[ October 06, 2005: Message edited by: Seb Mathe ]

Regards,<br />Seb<br /> <br />SCJP 1.4
Kenneth Albertson
Ranch Hand

Joined: Sep 18, 2005
Posts: 59
Originally posted by Anirvan:
What i can't quite figure out is, once the directory structure of a sub-directory is loaded into File[] dirs, how can it still hold on to the earlier directory elements?

You seem to be thinking of recursion as a form of looping, where the same local variables are used again and again. But that isn't how it works. Each recursive call is a new method call (just as it would be if it was a different method, not the same method), and a new stack frame and local environment is created.

So to answer your question, the initial array is still in the original dirs parameter, and the new array is in the new dirs parameter, in the new method call environment. And just as a method parameter and a class field can have the same name, but not be confused, there are two dirs parameters, and while the second method is executing, the first name is hidden. And so on for as many recursive calls as it takes.

Does that answer your question?
Anirvan Majumdar
Ranch Hand

Joined: Feb 22, 2005
Posts: 261
Thanks a lot Kym. I had been doing some research of my own too, and came across the concept of Heap and Stack.
Your explanation was really insightful and helped quite a bit. Thanks again.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Part of what you left out in "take some action" is creating a new list of files.

We create a new list and pass that in the recursive call. Every time you call a method the JVM allocates a whole new set of local variables in the method. Let's call the original method call depth 1 and the recursive call depth 2. The call at depth 2 has "dirs" pointing to level 1's "subList" and creates a new "sublist" of its own. When the call at depth 2 finds no more directories it exits and its set of variables is thrown away. The call at depth 1 resumes with its original set.

This is all pretty twisty to talk about. Is it making sense?


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Anirvan Majumdar
Ranch Hand

Joined: Feb 22, 2005
Posts: 261
Made perfect sense. Thanks to you too Stan
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Hi,

Welcome to JavaRanch!

A bit of business: you may not have read our naming policy on the way in. It requires that you use a full, real (sounding) first and last name for your display name. A single name isn't enough. You can change your display name
here.
Thanks!


[Jess in Action][AskingGoodQuestions]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursive algorithm doubt