Introducing Recursion
April 16th, 2008 | by admin | |Sooner or later, you will be confronted with a situation where you need to create an unlimited data structure. Think tree structures, where every new branch is an extension of another branch right the way back to the base of the trunk. Or even better, think family relationships, or parent/child relationships. We are often confronted with these types of situations in programming and the we must accommodate for a potentially unlimited amount of data. The answer to this common problem is called recursion, but before we look at recursion, I need to make sure you understand an unlimited data structure.
Storing Unlimited Data Structures
Storing such data is very simple. I’ll describe this in terms of nodes (parent and child nodes). For every node (that is unique, and has an id), we have a parent_id. The parent_id field is blank (or NULL) for the top level (or root level) nodes of data. This is where the tree of our unlimited data begins. Now that we have our root nodes, we can add new nodes, with the root nodes’ id as our parent_id. Suddenly we have child nodes of our root nodes, where we can now create yet another node, which is a child of our previous child node (which now becomes a parent node) and the cycle has begun.
To put it in visual terms, consider the following
root
…1
…2
……2.1
………2.1.1
………2.1.2
…………2.1.2.1
……….. (and so on, to infinity)
…3
……3.1
……3.2
…4
Figure 1.1: an example, potentially unlimited tree structure.
So now you can see how to easily form an unlimited data structure just by having a unique id and a parent id.
Now that you understand an unlimited data structure, you need to know how to display it. (For some projects, just storing the data may be enough, but for many cases, you will need to display it all in a structured way so users can see the parent/child relationships easily, in the form of a nicely formatted tree (as in Figure 1.1). Enter recursion 
Recursion is a very powerful and, if not written correctly, very dangerous programming logic (as it can lead to an infinite loop if you’re not careful). Recursion is the process of writing a function which calls itself. Yes, this can get confusing when you start thinking about it
Take a look at the following code that gets an array of files from the filesystem:
<?php
//recursive function to create an array of files from a physical directory
function get_files($directory_to_scan) {
//Try to open the directory
if($dir = opendir($directory_to_scan)) {
//Create an array for all files found
$tmp = Array();
//Add the files
while($file = readdir($dir)) {
//Make sure the file exists
if($file != "." && $file != ".." && $file[0] != '.') {
//If it's a directiry, list all files within it
if(is_dir($directory_to_scan . "/" . $file)) {
$tmp2 = get_files($directory_to_scan . "/" . $file, "/" . $file);
if(is_array($tmp2)) {
$tmp = array_merge($tmp, $tmp2);
}
} else {
array_push($tmp, "/" . $file);
}
}
}
//Finish off the function
closedir($dir);
return $tmp;
}
}
//kick off the process by calling the recursive function for the given folder
$values_array = get_files('/my_folder/pictures/')
?>
Do you see how the function calls itself when it has finished processing the given folder?
Recursive logic is especially useful with parent/child node data, or tree structures. With a small piece of code similar to the above example, regardless of how much data the users have entered and how deep the tree structure, we can easily conquer it by traversing all its elements, in order, from the top of the tree.
Real world example
This site’s menu system I have page categories that have a unique id (id) and can link to a parent page category (parent_page_category_id). From these two fields, I can establish a tree menu system. The functions I use for this are shown below. To kick this off, I just need to send the display_tree_menu function arrays of my menu items, page categories and pages. Doing this keeps SQL out of the recursive logic (which is important for performance).
<?php
/*
* @summary: This displays our tree menu, based on menu items, page categories and pages. This is all for a given menu item (one tree = one menu item). Kick this off by passing 0 as process_this_id
* @param: int (depth)
* @param: array (array of all menu items)
* @param: array (array of page categories for given menu item)
* @param: array (array of pages)
* @param: int (parent page category we are processing)
* @required_constants: SITE_MOD_REWRITE,SITE_LOCATION
*/
function display_menu_tree($depth, $menu_item_array, $page_category_array, $page_array, $process_this_id){
$depth++;
//loop through page categories
foreach($page_category_array as $key => $value){
//this is all for a given menu item (one tree = one menu item)
//only process
if($value->parent_page_category_id == $process_this_id){
//display category name, followed by articles within this category
if($depth == 1){
echo indent_depth($depth).' '.$value->name.' [HTML BREAK]';
} else {
echo indent_depth($depth).' '.$value->name.' [HTML BREAK]';
}
//show pages for given page category
foreach($page_array as $key2 => $value2){
if($key == $value2->page_category_id){
if(SITE_MOD_REWRITE == true){
//lookup menu item seo_name
$seo_name = $menu_item_array[$value->menu_item_id]->seo_name;
echo indent_depth($depth+1).' '.$value2->name.' [HTML BREAK]';
} else {
echo indent_depth($depth+1).' '.$value2->name.' [HTML BREAK]';
}
}
}
display_menu_tree($depth, $menu_item_array, $page_category_array, $page_array, $value->id);
}
}
}
/*
* @summary: This returns an indent string of our given length (used for the menu system)
* @param: int (depth to indent)
*/
function indent_depth($depth){
$returnvar = '';
if($depth > 1){ #skip first
while($depth > 1){
$returnvar .= '....';
$depth--;
}
}
return $returnvar;
}
?>