An explanation of recursive algorithms

Introduction to recursive algorithms

When developing software, often there are tasks that can be repeated. Every user in a program may perform the task of logging in, a program may have to process multiple items in a list similarly, or some other task comes up to be repetitious. In these situations, algorithms, which are a series of steps and actions, are very useful. One type of algorithm, a recursive algorithm, takes this concept and adds both complexity and usefulness.

Example 1 – Boxes within boxes

In a recursive algorithm, the task occurs again within the main task, possibly multiple times. This could sound very weird, so I’ll explain. First, I’ll simplify recursion. Abstractly, recursion could describe the process of opening a box, such as a Christmas present. In this situation, the task is to open a box to get the present. Recursion is what happens if the present contains a second, third, fourth, or more wrapped boxes contained within each box. So when each box is opened a new box is found. In this sense, the main task, opening the box, has more tasks, opening the boxes within the first box and subsequent boxes. So if a human had a set of instructions to open a box and get a present, they’d be able to reuse that set of instructions while they were still in the process of opening the original box and finding the present. In essence, the original task of opening a box occurred again during the task, or before task completion.

Example 2 – Tree structures

Recursive algorithms are useful for more than Christmas presents. Often, recursive algorithms are useful on tree structures, which are sets of data based on trees. Tree structures are visualized with the trunk being the main part, which then forks into numerous branches.  These branches further fork into smaller branches, and on and on until the leaves or end of the branches are reached. If each branch was assigned a task, such as look at the leaves, then a recursive algorithm for the task could start with looking at the trunk, and trace each branch until the end.  Then, the algorithm would continue to the next branch until each branch end was examined.  At some points, the algorithm’s task would be looking at branches immediately smaller than the main trunk, and sometimes five or more levels of branches smaller. Yet at each level, the task of looking for a branch end or continuing along a branch would be an effective way of finding each branch end in the tree.

In reality, tree structures are useful for organizing a vast variety of data in fields such as science, business, engineering, math, and so on.  Just think galaxies to solar systems to stars and planets to molecules to atoms for worlds of scientific tree structures.  But computer science is what allows for fast and automated processing of tree structures of data with software.  In a software design, recursive algorithms can perform repeated and complex tasks on tree structures.

Example 3 – Directory structure

One common example of a tree structure in computer science is the directory system of a computer’s hard disk. Folders exist within folders like tree branches contain smaller branches.  Files are placed at various intervals like leaves of branch ends.  At the foundation of the system is a main folder, or hard drive root, containing all the files and folders.  Like the previous recursive algorithm of examining a tree branch by branch, a computer program with a recursive algorithm could effectively go through every file and folder on a hard drive looking for task objectives and goals. At any given point of the search, the program would be looking inside of a folder, similar to how the previous viewer was looking at one part of a branch at a time, yet processing the entire tree.

Recursive Algorithm Design For File Searching

Those three examples are meant to convey some ideas and concepts of recursion and algorithms.  To achieve recursion within a computer program, a function, subroutine, or method must execute itself within itself. For the files and folders example, the recursive algorithm could be named something like recursiveFileSearch with the parameters of start_folder and search_file.

The following algorithm design could describe the function:
(1) Search for search_file within start_folder.
(2) If found, return information about search_file.
(3) If unfound, make a list of subfolders in start_folder.
(4) (a)Send each subfolder as the folder parameter into recursiveFileSearch function until the function returns a find or ends.

(4) (b) Also send the original search_file  as a parameter.

This four step algorithm implements recursion because at stage 4, the algorithm is performed again within itself.  At stage 4, the function merely sends a subfolder argument to a copy of itself.  The function will literally search all available files and folders within the folder originally sent to it for the original filename.

Of course on a real computer, file permissions, operating system pathnames, language specifics and more can complicate the algorithm when converting it to code.  However, in pseudo code, the algorithm can be shown in ways that are language independent and simplified.

This function isn’t programming language specific, and is only meant to show how a recursive algorithm might look as part of a program.  The function accepts a folder to search in and a file to search for as parameters.  Then, the foreach loop goes through each item in the folder.  If the item is the file being searched for, it returns the file data and exits the function.  Next, if the item is a folder, then the function calls itself again with the subfolder as a parameter.  So basically, each subfolder of the original folder argument will result in a recursive call of the function, and each subfolder of each subfolder also.  If any recursive call returns a found file, then the original function call returns the found file also.  Depending on objectives, the function could return a full pathname, relative pathname, filename, or simply true or false to indicate whether the file exists or not.

Implementations of Recursive Algorithms for File Searching

/**
* 7-7-2013 Copyright Scott Taylor - written for scottscompsci blog.
* Performs a recursive search for a file in a given directory.
* @param start_folder A File object referencing the folder to start the
* search in.
* @param search_file A String object with the filename to search for.
* @param verbose A boolean value specifying whether to print
* output messages or not.
* @return The return is a File object either containing the
* found file or a non-existing file.  File objects
* contain information about the file path, name,
* and more.  If less information is required the
* return type could easily be modified to a true or
* false value.
*/
public static File recursiveFileSearch( File start_folder,
                                        String search_file,
                                        boolean verbose )
                                        throws FileNotFoundException
{
    // Throw an error if not starting in a valid directory.
    if ( !start_folder.isDirectory())
        throw new FileNotFoundException();

    // Makes an array of all the files in the starting directory.
    File[] file_array = start_folder.listFiles();

    if ( verbose ) System.out.println( "Searching for " + search_file +
                                       " in directory " + start_folder);

    // Loops through each file in the starting directory, and performs
    // recursive searching through subfolders.
    for ( int i = 0; i < file_array.length; i++ )
    {
        if ( file_array[i].isFile() )
        {
            if ( file_array[i].getName().compareTo( search_file ) == 0 )
            {
                if ( verbose ) System.out.println( "Found " +
                               file_array[i].getAbsoluteFile() );
                    return file_array[i];&nbsp; // Returns the find.
            }
        }
        else if ( file_array[i].isDirectory() )
        {
            // Sends the file_object directory back into this function
            // as the new start_folder.
            File file_object = recursiveFileSearch( file_array[i],
                                                    search_file,
                                                    verbose );

            if ( file_object.getName().compareTo( search_file ) == 0 )
                return file_object;&nbsp; // Returns the find.
        }
    }

    // Didn't find the file, return a non-existing File object.
    return new File("");
}

 

/**
* 7-8-2013 Copyright Scott Taylor - written for scottscompsci blog.
* Performs a recursive search for a file in a given directory.
* param start_folder A string referencing the folder to start the search in.
* param search_file A string with the filename to search for.
* param verbose A boolean value specifying whether to print output messages or not.
* return The return is a pathname object either containing
* the found file or an empty string. If less
* information is required the return type could
* easily be modified to a true or false value.
*/
function recursive_file_search( $start_folder,
                                $search_file,
                                $verbose )
{
    // Throw an error if not starting in a valid directory.
    if ( !is_dir( $start_folder ) )
        throw new Exception( 'Folder ' . $start_folder .
                             ' not found.' );

    // Makes an array of all the files in the starting directory.
    $file_array = scandir( $start_folder );

    if ( $verbose )
    {
        echo "Searching for " . $search_file .
             " in directory " . $start_folder . "\n";
    }

    // Loops through each file in the starting directory, and performs
    // recursive searching through subfolders.
    foreach( $file_array as $file )
    {
        // Don't use filenames of . and .. which indicate present and
        // parent directory. PHP's scandir() returns these.
        if ( $file == '.' || $file == '..' )
            continue;

        // Makes sure to include any previous folders.
        $file_path = $start_folder . DIRECTORY_SEPARATOR . $file;

        // Checks if this is the file searched for.
        if ( is_file( $file_path ) )
        {
            if ( $search_file == $file )
            {
                if ( $verbose ) echo "Found " . $file_path&nbsp; . "\n";
                    return $file_path; // Returns the find.
            }
        }
        else if ( is_dir( $file_path ) ) // Searches within folders.
        {
            // Sends the file_object directory back into this function
            // as the new start_folder.
            $found = recursive_file_search( $file_path,
                                            $search_file, true );

            if ( $search_file == basename( $found ) )
                return $found; // Returns the find.
        }
    }
    // Didn't find the file, return an empty string.
    return "";
}

Ideas for future additions to this blog article include example functions in more programming languages.

Feel free to link to this article and use the example functions if you like.
If you liked the blog please like, share, or comment.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s