[OT] Get directory structure without using recursion

  • Thread starter Thread starter John Baro
  • Start date Start date
J

John Baro

Is there any way of getting a directory structure of unlimited levels
without using recursion?
GOTO is not an option.
I cannot think of any way but I am not the smartest cookie in the crumble.

TIA
JB
 
John said:
Is there any way of getting a directory structure of unlimited levels
without using recursion?
GOTO is not an option.
I cannot think of any way but I am not the smartest cookie in the crumble.
Click to expand...

Recursion can be replaced with stack usage.

Something like this: (pseudocode)

ArrayList list = new ArrayList();
Stack s = new Stack();

....
// put current level items into stack

string[] files;
while(s.Count>0) {
string file = s.Pop();
list.Add(file);
files = Directory.getChildren(file);
s.Push(files);
}

// now list contains all items

Vadim Chekan.
 
John Baro said:
Is there any way of getting a directory structure of unlimited levels
without using recursion?
GOTO is not an option.
Click to expand...

Hmmm, why is GOTO not an option? Are you forbidden to use it by a
fetishistic boss? I coded two C# goto statements just last night... (With
comments saying I'm a professor of computer science and nobody can tell me
not to! :)

What you are wanting to do is a tree search. If you can't write recursive
procedures, then the other way to do it is to maintain a list of directories
you're going to search. Initially it contains only the current directory.
Find the directories in it and add them to the end of the list. Keep going,
and keep doing the same thing. Or add them at the beginning, if you'd
rather have a depth-first search.

More generally: Any recursive algorithm can be implemented without
recursion, by using additional lists or stacks. After all, there is no
recursion in machine language; the compiler has to translate the recursion
into something else. The Pentium has stacks in machine language, but some
other machines I've used (e.g., CDC CYBER) do not. Just more work for the
compiler.

In the *really* old days (pre-1980 or so) most programming languages did not
allow you to write recursive procedures. Try writing an expression
evaluator in FORTRAN. I did; I think it had 3 stacks.
 
John Baro said:
Is there any way of getting a directory structure of unlimited levels
without using recursion?
GOTO is not an option.
I cannot think of any way but I am not the smartest cookie in the crumble.
Click to expand...

You could maintain a list of directories you've retrieved, along with
an index into the list which represents the directories you've then
found the subdirectories of. Keep working through the list, adding
entries to the end and gradually moving through it, until you hit the
end of the list.
 
Hi John,

IIRC from my class of data structure and algorithm you have a tail
recursion, and it can be substitute with the use of a Queue and a stack. (
I'm not sure rigth know if any recursion can be implemeted with these or
only the tail one, maybe I dont remember it very good after all :) )

anyway, if you want to maintain the structure for later use you may use a
tree for it.

Cheers,
 
Ignacio Machin ( .NET/ C# MVP ) said:
IIRC from my class of data structure and algorithm you have a tail
recursion, and it can be substitute with the use of a Queue and a stack. (
I'm not sure rigth know if any recursion can be implemeted with these or
only the tail one, maybe I dont remember it very good after all :) )
Click to expand...

This is not tail recursion, because a directory can have any number of
directories in it. If each directory could contain files and only one more
directory, you'd have tail recursion, and you could simply do the
sub-directory last.

In any case, all recursion can be done with stacks or queues, without
recursive functions. There are whole programming languages (e.g., FORTRAN)
where you have to do it that way.


--
 
Back
Top