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:
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..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; } }
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):
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 $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; } }
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; push @stack, glob("$entry/*"); }
use strict; use warnings; my @stack = @ARGV; while (my $entry = shift @stack) { print $entry, "\n" and next if -f $entry; unshift @stack, glob("$entry/*"); }
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.
In reply to Re^4: Recursive Directory print
by Laurent_R
in thread Recursive Directory print
by zavo
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |