http://www.perlmonks.org?node_id=151693


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

Replies are listed 'Best First'.
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