Support : Guides

Recursion

One of the most powerful coding techniques to master is "recursion". The process exploits the capability of modules and subroutines to manage separate memory sections specific to the scope from which they are executing taking advantage of dynamic memory allocation and deallocation.

The example below shows how to loop through a subdirectory and process all of the files and subdirectories contained in it. And, while process the subdirectories, also process all of the files and subdirectories in each. And, continuing the process deeper and deeper until all files and subdirectories have been processed.

The example consists of definition of two global variables and invocation of two subroutines; proc_files and proc_dirs. Within each subroutine local variables are defined one receiving an input value and the other being an array that receives the list of files or directories from the "readdir" command (PERL built-in function). GREP is used against the output of the "readdir" command to restrict the results to either files (using the "-f" switch) or directories (using the "-d" switch.) Then, in each of the two subroutines the array receiving output of the GREP qualified "readdir" command are processed.

The "recursion" occurs within the "proc_dirs" subroutine where "proc_dirs" calls itself. It passes a new parameter on the recursive call. The current array (@d), as well as the "foreach" internal counters and pointers and their current state are preserved. This means that upon completion of the recursive call, when control is returned back to "proc_dirs" in its initial state, the next @d element will be processed within the "foreach" loop.

What is occurring in this recursion process is a series of "instances" of the "my" scoped variables are being dynamically generated in memory for each recursive call. At the source code level this can be confusing, but after realizing that internally each "my" variable instance is being associated with the specific call. And, those instances are being managed internally so that upon return to the calling instance the variable references are specific to that instance's state.

The output of the example below produces a list of the directory paths and filenames of all ".htm" and ".shtm" files contained within the subdirectory assigned to the $base variable.

#!/usr/local/bin/perl

$base = "/home/users/myspace/html/";
$delim = "/";

proc_files($base); 
proc_dirs($base);  # Prime the recursive call

print @out;

exit(0);

sub proc_files ($)
{
    my $subdir = shift;  # Called iteratively by proc_dirs
    my @files;

    opendir(DIR,$subdir);
    @files = grep{-f $subdir.$_;/\.html$/;} readdir(DIR);  # HTML files
    closedir(DIR);

    push(@out,"$subdir$_\n"); # stack result
}

sub proc_dirs ($)
{
    my $path = shift;  # Called by itself recursively
    my @subdirs;

    opendir(DIR,$path);
    @subdirs = grep {-d $path.$_; !/^\./} readdir(DIR);  # subdirectories
    closedir(DIR);

    foreach (@subdirs) {  # Process subdirectory files
        push(@out,$path.$_.$delim."\n");
        proc_files($path.$_.$delim);
        proc_dirs("$path$_$delim");  #  RECURSIVE CALL
    }
}

NOTE: The example above uses several shorthand PERL syntax in order to simplify this illustration of recursion.