Re: Re: Unrolling recursion

[clintp]

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

[broquaint]

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