Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
Welcome to the Monastery
 
PerlMonks  

Re: Re: Unrolling recursion

by clintp (Curate)
on Mar 14, 2002 at 15:15 UTC ( #151693=note: print w/ replies, xml ) Need Help??


in reply to Re: Unrolling recursion
in thread Unrolling recursion

From a /msg request for dragonchild, here's pseudocode to do a directory traversal without recursion.

# Traverse the filesystem push to stack / while currentdirectory = pop stack open the currentdirectory foreach pathname in this directory if it's also a directory, push it (full path) on the stack close the current directory
As opposed to a recursive solution:
call traverse(/) function traverse (currentdirectory) open currentdirectory foreach pathname in this directory if it's also a directory, traverse(pathname) close currentdirectory


Comment on Re: Re: Unrolling recursion
Select or Download Code
Re: Re: Re: Unrolling recursion
by broquaint (Abbot) on Mar 14, 2002 at 15:47 UTC
    For those who don't grok pseudocode here's a perl translation for directory traversal without recursion
    my @stack = "."; while(my $cd = pop @stack) { opendir(my $dh, $cd) or die("bad dir - $!"); foreach (readdir($dh)) { next if /^\./; print $_.$/; push @stack, "$cd/$_" if -d "$cd/$_"; } }
    and with recursion
    &traverse("."); sub traverse { my $dir = shift; opendir(my $dh, $dir) or die("bad dir - $!"); foreach (readdir($dh)) { next if /^\./; print $_.$/; &traverse("$dir/$_") if -d "$dir/$_"; } }
    That's a pretty neat 'trick' which I guess might be how optimising compilers implement some forms of recursion (or something).
    HTH

    broquaint

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://151693]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2014-04-18 00:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (460 votes), past polls