Introduction
"To understand recursion, you must first understand recursion."
"To make yogurt, you need milk and yogurt."
If you are not accustomed to use recursion, some aspects of it might initially seem as senseless as the above statements (the second one is actually a true statement), or as the story of Münchhausen, who got himself and his horse out of the swamp, by pulling his own hair.
However, there is really nothing mysterious about recursion.
What is it all about?
Well, even if you did only the most basic programming (in Visual FoxPro or otherwise), you probably already know that one function can call another function. (Note: in Visual FoxPro, for practical purposes there is no difference between a function and a procedure. I will use the word "function" in this text.) That is to say, Function_A can call Function_B:
FUNCTION_A * Some preliminary code Function_B() * Some additional code ENDFUNC
Well, there is nothing that forbids a function to call up itself:
FUNCTION_A * Some preliminary code Function_A() * Some additional code ENDFUNC
The fact of a function calling itself is called "recursion".
At least three important considerations apply, when you use recursion:
First, all variables have to be declared as local or private. Otherwise, the different instances of the function will overwrite each other's variables. Of course this is proper programming practice anyway, but in the case of a recursive function (that is, one that calls itself), it is a must. With local or private variables, each instance of the function will have its own copy of the variables.
Second, there has to be some condition, implicit or explicit, to end the recursion - otherwise, the program will end up going deeper and deeper (into more and more levels), and never finish.
Third, most programming languages have limits as to how many levels programs can call each other. This limit applies whether one function calls another function, or itself. In Visual FoxPro, this is limited to 128 levels. This can severely limit the scope of recursion. The reason this limit exists is because the executing program has to store information, in a stack, about each executing function - and this stack often has a fixed size.
A primitive example
An example often given for recursion is the factorial function. For instance, the factorial of 5, written as 5!, is defined as 1*2*3*4*5 (multiply all numbers up to the specified number). By the way, 0! is defined as 1.
It is easy to verify, for instance, that 5! = 5 * 4!. But this is, precisely, a recursive definition (the calculation of the factorial of 5 includes the factorial function). The Visual FoxPro code is:
FUNCTION FACTORIAL(number) if number = 0 return 1 else return number * factorial(number-1) endif ENDFUNC
Please note that this is not the most efficient way to solve this particular problem. It is just an illustration of recursion. First, this can easily be solved by a loop - and a program calling itself has much more overhead. Second, we are limited to factorials of small numbers, because of the Visual FoxPro limitation of 128 DO levels.
The loop version, without recursion, might look like this:
FUNCTION FACTORIAL(number) local i, factorial factorial = 1 for i = 1 to number factorial = factorial * i next return factorial ENDFUNC
This version is about as complicated as the first version. However, and although in theory any problem that can be solved with recursion can also be solved without recursion, there are problems that turn out to be very difficult to manage without recursion.
Subfolders
I will now show a more relevant example. It turns out that recursion is ideally suited to do processing in certain cases where there is a natural hierarchy in the data.
One such case is the manipulation of folders that contain subfolders. The definition itself of "folder" is recursive: from the logical standpoint, you can use a definition similar to "A folder is a unit in which you can store files, and other folders". So, using recursion in your programming seems quite natural when you try to process the files - how should I say - "recursively", that is, including all subfolders at different levels.
The following example will list all files with a certain extension on your hard disk. You could easily change it to some other action, for instance, delete *.BAK.
* Sample of recursion with folders: list all files like *.BAK for an entire disk. local lcExtension, lcStartFolder lcStartFolder = "c:\" lcExtension = "BAK" ProcessFolder(lcStartFolder, lcExtension) FUNCTION ProcessFolder(pcStartFolder, pcExtension) * Process all files in the specified folder, including subfolders local i, laFiles(1) for i = 1 to adir(laFiles, pcStartFolder + "*.*", "D") do case case laFiles(i, 1) == "." or laFiles(i, 1) == ".."
* Ignore entries for current folder and parent folder case "D" $ laFiles(i, 5) && it is a directory (folder) ProcessFolder(pcStartFolder + laFiles(i, 1) + "\", pcExtension) case upper(justext(laFiles(i, 1))) = upper(pcExtension) ? pcStartFolder + laFiles(i, 1) endcase next ENDFUNC
Note that I stated earlier that there has to be some condition to end the recursion. In this case, the condition comes quite naturally through the structure of the underlying data: the function only calls itself if there are sub-folders. At some point, a folder has no further subfolders to process.
Unlike the factorial, this example is more difficult to process without recursion.
Business logic
You can also use recursion profitably to process all kind of business logic - if there is some kind of hierarchy in your data, you can define and program certain processes recursively. (To actually show the data hierarchically, you might use a treeview control, which allows the user to open and close individual branches. For instance, the treeview control is used in Windows Explorer, to show folders recursively.)
One example of hierarchical data is the accounts used by the accounting department (an account can contain several sub-accounts, and this can continue, through several levels).
Another example is in a manufacturing process: a finished product contains materials. However, a finished product can also contain intermediate products, and these intermediate products then contain the raw materials. This can continue through several levels, where an intermediate may contain other intermediate products.
The advantages of being able to create intermediate products are huge, especially if the intermediate product is used in several places. By creating intermediate products, the data for the intermediate product has to be defined only once. Otherwise, the same listing of raw materials, for what otherwise would be an intermediate product, would have to be repeated in all finished products.
Recursion can be used for several purposes here. For instance, when the user edits the list of materials by product (where either the material, the product, or both, can also be an intermediate product!), you should have validation rules to ensure that a product doesn't contain itself - either directly or indirectly (for instance, "A" contains "B", "B" contains "C", and "C" contains "A"). A product containing itself is an invitation to disaster. This check requires searching (recursively, of course) through the materials contained in the product.
Another use of recursion for the manufacturing process is to produce a list of required raw materials for a certain set of finished products that should be produced. This may be required to purchase the raw materials, or to check whether we have enough of everything in our warehouse. Again, the materials by product have to be processed recursively - this time, multiplying quantities to be produced, by the quantity of the material used in each product.
Some of the details of such a manufacturing process are quite complex, even if you use recursion. Recursion does help a lot, though, to make this sort of problem more manageable.
Summary
As you can see, several problems involving a hierarchy of data, that may look unmanageable at first, in fact turn out to be relatively simple if you use recursion.
