Simple Recursion

I wrote in an earlier post about the useful programming technique of recursion. I have learned a lot about programming since then, and one regret I have about my earlier post is that the example code is too long and complex to clearly describe the simple point I was trying to make.

So here's another try, with some much simpler examples.

What is recursion?

Many Cocoa programmers are self-taught, and recursion is the kind of "thinking outside the box" technique that may not occur to even the most experienced coder.

The basic technique involved in recursion is that of a method calling itself. It is a form of self-reference which allows us to take a shortcut to our desired result.

What does this mean? Breaking it down, it means that the recursive method will look something like this:

-(BOOL) doSomething:(BOOL)flag
{
    if (flag == YES)
    {
        doSomething:YES; //[1.6]
    }
    else
    {
        return NO;
    }
}

At line [1.6] this method calls itself.

Notice that this method will loop forever if it is sent YES as the argument. As a consequence, the program that contains it will hang at this point and need to be forced to quit before it eats all the memory available to it. The trick to using recursion in your code is simply to make sure this never happens. In practice, this thankfully turns out to be quite simple.

Why use recursion?

Recursion is an extremely useful technique for any programmer to have in their repertoire. Technically speaking, it makes it easy to traverse a tree of unknown length.

Consider the following example:

-(void) newArtFromFolder:(NSString *)importFolder
{
    BOOL isDir;
    id importFile;
    NSDirectoryEnumerator *dirEnum =[[NSFileManager defaultManager] enumeratorAtPath:importFolder];
    while (importFile = [dirEnum nextObject])
    {
        isDir = NO;
        if ([[NSFileManager defaultManager] fileExistsAtPath:importFileisDirectory:&isDir] && isDir)
        {
            // This is a nested folder: Recursive call
            [self newArtFromFolder:importFile];         //[2.12]
        }
        else if ([[importFile pathExtension] isEqualToString: @"itc"])
        {
            // This is an itc file: Extract the art
            [self newArtFromFile:[importFolder stringByAppendingPathComponent: importFile]];
        }
        else
        {
            NSLog(@"Wrong kind of file");
        }
    }
}

To break this simple piece of code down, we have two branches. One tests if importFile is a folder, and if it is, passes it back to this very method for another round [2.12]. If instead is a file with the extension ".itc" it gets passed off to another method to handle the next step. Otherwise, nothing happens.

It is certainly possible to write a method which achieves the same results without using recursion, however it would necessarily contain more lines of code and be more difficult to write, maintain and debug. The advantage of using recursion in this case is that we don't need to know beforehand how many levels deep in the folder tree we might need to search, any folders which are found in the search will simply be passed back through until we reach the file level.

In this example we don't need to worry about endless looping because in practise every tree of folders will be finite. Eventually we will run out of folders and the recursion will no longer be called, thanks to our if statement.

Conclusion

Recursion is a useful technique for solving problems which require sorting or searching through an arbitrary length tree.

References

This article contains code from ArtDeCodex. To see the code described above in a working context, please download the source code and have a look in AlbumArtController.m.

Post new comment

The content of this field is kept private and will not be shown publicly.
Enter the code shown in the image:

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
8 + 8 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Donate!





If you like what you find here and wish to support further development of this site, please donate via PayPal. No account required.

Syndicate

Syndicate content

User login

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
6 + 0 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.
Enter the code shown in the image: