Recursion is a beast. I hated recursion until I fully understood it, which is what I will try to do for you in this tutorial. To make the "medicine go down", I will use the example of a directory tree (common ground for all).

Recursion is fundamentally a method calling itself. This may seem pointless and prone to infinite loops, but it is actually the best, and sometime "only", way of solving a problem. Any problem can be solved without recursion, but some of these can only be solved by "faking" recursion with stacks.

Well, what is recursion and how do we use it??


Defining Recursion
All recursive methods must have a base case. This base case is the point at which recursion will end. Without a base case, the recursive method will devolve into an infinite loop, and nobody wants that. The base case should be checked first, and then the regular case.

To use recursion, you must define the structure in which you are recursing in terms of itself. Let's look at directory trees to get a grasp of this abstract concept:

Each folder has children. To get through a directory tree, we must pick a child at each level. This child has children, and each of its children have children until you get to a folder with only files. Say you want to copy a file from somewhere down the tree to the place in which you started. You start at the top, presumably C:\ or My Documents, and go through each level following a path to get to your specified file. At each level, you pick a child and open it. You continue in this until you get to your file of choice. Upon finding this choice, you bring a copy up each level of the path until you get to the top of the tree, where you deposit the file in question.

This is recursion in its most elemental state. Recursion can be used in many different pursuits- linked lists (very common), trees (Binary Search Trees, directory trees), XML files (using XPath), sorting, etc.

Now that we know what it is and what it can be used for, how do we implement it?


Using Recursion
In this section, I will walk you through how to create a recursive directory listing, displaying all folders. This program will not be complete, but it will set up the structure for such a listing. Basically, you will have to come up with how you want it displayed; I will show how to visit every folder in a directory tree.

First, we must define folder: a folder consists of files and child folders. Wow, this is just begging for a recursive program. Now that we have a working definition, we must make a base case. Our base case for this program will be a folder that has no child folders. Here's our code so far (written in Java):

Now we need to make it do something. For that, we will add in code that will do the following:

1. Print the current Folder- this will include any files that are in the folder
2. Print the folder's children- call printTree() with each child folder

Ending Thoughts
Recursion is a very powerful tool for dealing with structured information effectively. Recursion should not be used when it can be avoided because it is a memory hog- each recursive call puts another item onto the system runtime stack. Having too many recursive calls will noticeably slow performance of your program. Recursion will almost always be more computationally intensive than a non-recursive solution, but the simpleness of the code often makes up for this time delay.

I have used recursion in many solutions including: searching for items in a tree, sorting algorithms, linked lists and others. The key thing to keep in mind is to "trust the recursion". This means to think about the current step and the next step and trust that it will work correctly. Make sure to test any recursive code, as, like any other programming topic, any small mistake can cause huge problems down the line.

Good luck!!

 

 

 

Reply