please read a correct recursive implemntation by tachyon here.

Hmm, I am sorry, but tachyon's solution to which you refer is most probably correct, but it is not recursive (a recursive algorithm implies that a subroutine calls itself, there is not even one function call in tachyon's solution.) Actually, even tachyon admits that it is not recursive. (Which, of course, doesn't mean in any way it is bad, it is just not recursive and therefore does not fit the OP's bill of requirements.)

wow.. vey good point.. thanks Laurent_R.

The central point, as many times, is a correct understanding of words and semantic they cover.
This can be useful for the OP and for other as me that have missed this difference (from wikipedia):

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem
Iteration is the repetition of a block of statements within a computer program
That said obviously the tachyon solution falls in the iterative category..

#excert from tachyon's code at http://www.perlmonks.org/?node_id=15785
+1
my @dirs  = ($root);

for my $path (@dirs){
    opendir ( DIR, $path ) or next;   # skip dirs we can't read
    while (my $file = readdir DIR) {
      next if $file eq '.' or $file eq '..'; # skip dot files
           if ( -d $path.$file ) {
            push @dirs, $path.$file.'/';     # add dir to list
        } 
    }
    closedir DIR;
}
[download]

but..
..the logic of the snippet IS recursive in the way it populates @dirs: in fact it iterates over a list updated dynamically while processing the iteration itself. It produes a directory tree, or well a list of different depth objects. Also here the problem is divided in small pieces to process. But in the opposite way: @dirs starts populated by the root node only and while it is processed the stack @dirs itself it is updated: the way @dirs is populated by push seems recursive, in a broad sense.

In other words, as wikipedia tell us some line below:

Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion.


Hth
L*
There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

I understand your point, but I still have to disagree in part (this disagreement did not prevent me from upvoting both your posts, as they are very interesting anyway).

Consider the difference between the excerpt from tachyon's code you've just published in your post and the truly recursive solution I proposed in this post: Re: Recursive Directory print, which I'll repeat here for convenience:

use strict;
use warnings;

search_dir (shift);

sub search_dir {
    my $path = shift;
    my @dir_entries = glob("$path/*");
    foreach my $entry (@dir_entries) {
        print $entry, "\n" if -f $entry;
        search_dir($entry) if -d $entry;
    }
}
[download]

The search_dir is initially called with the root dir to be explored and then, anytime the code meets a dir, search_dir is called recursively to explore that dir. This is real recursion..

In the code you posted above, the @dirs array is playing the role of the explicit stack that is mentioned in your quote from Wikipedia about shifting from recursion to iteration (although, in that case, it is not exactly a stack, items are added to it, but never removed from it). So it is really iterative code. But when you want to traverse a tree with iteration, you always need something like that: an array or a stack where you need to store the entries that you still need to process

The good thing about recursion is that it often leads to simpler code (well, at least shorter code, but also simpler to understand once you have grasped the idea of recursion, which some people have initially difficulties to do). It is also a more natural way of applying the divide and conquer strategy (divide a problem into smaller problems that are easier to solve). The downside of recursion is that it basically forces you to traverse a tree depth-first, which is sometimes not what you need. Another downside, contrary to what the quote from Wikipedia implies is that recursion uses often more resources than iteration, because the execution stack of a deeply nested recursive procedure tends to be more expensive than the simple explicit stack of an iterative process.

Tacheon's code, in contrast, is a breadth-first tree traversal, which is usually the most natural way with an iterative algorithm. But it would not be too difficult to change things to make it a depth-first exploration.

Update : I did not have time when I wrote the above to do this, but I can now update. This is how I could transform my recursive procedure above into an iterative one using an explicit stack (which I called @stack to make things clear in this specific context; in real life, I would probably call it something like @unprocessed_dirs to make its functional content clearer):

use strict;
use warnings;

my @stack = @ARGV;
while (my $path = shift @stack) {
    my @dir_entries = glob("$path/*");
    foreach my $entry (@dir_entries) {
        print $entry, "\n" if -f $entry;
        push @stack, $entry if -d $entry;
    }
}
[download]

This code is doing a breadth-first traversal (just like tachyon's code), i.e. for every directory, it lists all the files in that directory, and then only proceeds to start visiting the subdirectories (in the order in which they were met). With this approach, it is a bit difficult, though, to shift to depth-first traversal. Let's take a modified approach which simply stores in the stack every entry found and processes elements taken from the stack. This code is simpler and is also giving a breadth-first traversal:

use strict;
use warnings;

my @stack = @ARGV;
while (my $entry = shift @stack) {
    print $entry, "\n" and next if -f $entry;
    push @stack, glob("$entry/*");
}
[download]

Now, to shift from breadth-first exploration to depth-first exploration is matter of changing only the last line of the code:

use strict;
use warnings;

my @stack = @ARGV;
while (my $entry = shift @stack) {
    print $entry, "\n" and next if -f $entry;
    unshift @stack, glob("$entry/*");
}
[download]

BTW, our @stack array now really behaves as a stack (last in, first out), while, in the previous version, it really acted as a queue (first in, first out).

Mark-Jason Dominus has a full chapter on eliminating recursion in his excellent book, Higher Order Perl.