Fundamentals of Recursion in PHP

Iteration is a straightforward concept. Recursion is a bit more complicated; it can be defined as a regular function that calls itself. PHP supports recursive functions. This article, the first of three parts, will explain recursive functions and help you see why they are useful.

Introduction

Although you’ve probably never turned your attention to counting the number of situations where you used iteration during the development of a Web application, writing iterating code is certainly a thing that you’ve done hundreds, not to mention thousands of times.

Iteration is a direct consequence of the ability of computers to automate repetitive tasks, something that has been reflected in most programming languages with the introduction of different iteration structures. In fact, the issue is as simple as it seems: if there’s something that you need to do the same way a number of times inside an application, then you’ll use some kind of loop structure to repeat several blocks of code.

With reference to executing repetitive code, PHP supports the use of the popular “for,” “while,” “do-while” loops and additionally the “foreach” loop, which can be used to easily traverse arrays. Also, there are a few additional built-in functions that perform some sort of iteration on data structures, such as the “array_map()” function, to cite a well-known example. Still, in this article, I’m definitely not going to bore you with an irrelevant list of iterating PHP functions, since you can read the corresponding manual.

In general terms, iteration is a pretty straightforward concept, which as you saw, can be applied in different programming cases with minor hassles. However, let me go one step further in my explanation: say you’ve defined a PHP function that need to be called repetitively within an application, in order to traverse dynamic data structures such as trees or linked lists. In this case, you’re likely to use what is commonly called a “recursive function.”

Essentially, a recursive function can be defined as a regular function that calls itself. Sounds like a confusing concept? It isn’t. Fortunately, PHP supports the definition of recursive functions, which can be useful in certain situations. For instance, you’ll want to use a recursive function if you’re going to do a lot of work with data trees, which are structured as database tables, or in cases where template files contain nested placeholders and need to be recursively parsed, and so on. You get the idea.

Considering the important role that recursion plays in most programming languages, and specifically in PHP, over this series I’ll be demonstrating how to define and use recursive functions with numerous code samples, thus you can learn quickly how to include them in your own PHP scripts.

Curious about using recursion in PHP? Let’s get started and not waste more time. 

{mospagebreak title=Introducing the basics of recursion: developing an easy-to-grasp example}

To start illustrating the basic concepts of recursion in PHP, first I’ll show you some friendly examples of recursive functions. In this way you can acquire a solid knowledge of the topic. Please study the first example listed below, which uses a recursive function to deeply traverse an array structure and save its elements to a sample text file:

// recursive function to traverse arrays and save elements to
file
function arrayToFile($inputArray,$file){
    foreach($inputArray as $element){
        if(is_array($element)){
            // call recursively the ‘arrayToFile()’ function
            arrayToFile($element,$file);
        }
        else{
            if(!$fp=fopen($file,’a+’)){
                trigger_error(‘Error opening data
file’,E_USER_ERROR);
            }
            fwrite($fp,$element.”n”);
            fclose($fp);
        }
    }
}

In the above example, you can see that I defined the recursive “arrayToFile()” function, which is tasked with taking up an incoming recursive “$inputArray” array and storing each of its elements in the “$file” text file. Although its definition is rather trivial, this function helps you see in a nutshell how recursion works. Notice how the function calls itself, in order to navigate the respective input array and save all its elements to the specified file.

Here, there are some important points to consider regarding this example, and of course, the subsequent ones: first, each time the function calls itself, it makes a copy of its source code in the server. This means that different instances of the function will be maintained in memory, preventing the PHP interpreter from being confused about what instance to handle.

Secondly, when each function call has finished saving an array element to file, program control is returned to the instance that called the function, until finally control is moved back to the main routine. In accordance with these concepts, it’s clear to see that a recursive function is much more resource consuming than traditional iteration, since it needs to make copies of itself in memory.

Finally, even when recursion can be used as a more professional approach for solving specific programming problems, its drawbacks reside mainly on the potential overhead of multiple function calls, and the difficulty many programmers have in coding an ending condition for the recursive process. This leads very often to making a function recur indefinitely, until the timeout for the script is reached, or eventually until the server runs out of resources (specifically RAM memory).

Having explained in detail the particulars of how recursion works internally, it’s time to show how to use the “arrayToFile()” function that I defined above. Here is a brief example that demonstrates the capacity of this simple recursive function:

// define recursive array
$data=array(‘element1′=>1,’element2′=>2,’element3′=>array
(‘recursive_element1′=>3,’recursive_element2′=>4,
‘recursive_element3′=>array(‘key1′=>’This is an example of
recursion’,'key2′=>’This is another example of
recursion’)),’element4′=>4);
// save array elements to file
arrayToFile($data,’data_file.txt’);

As shown above, I first defined a recursive array, that is, some elements are also arrays, and next passed it as an argument to the “arrayToFile()” function, in order to store each element in a sample “data_file.txt” text file.

The contents of this file, after running the above script, are listed below:

1

2

3

4

This is an example of recursion

This is another example of recursion

4

As you can see, the function has gone deeply through the $data recursive array and stored the corresponding elements in the sample text file. Hopefully, this basic example should give you a pretty clear idea of how a recursive function can be defined in PHP. Nevertheless, recursion is best understood by thorough practice. That’s precisely what I’ll try to provide you in the next few lines, thus please click on the link below to see more examples of how to write recursive functions in PHP.

{mospagebreak title=Emphasizing the fundamentals of recursion: defining an improved recursive function}

As I said before, recursion is a topic that is best understood by example. Keeping in mind this idea, below I coded a new version of the “arrayToFile()” function that you learned before, which is slightly more understandable. Please have a look at its respective signature:

function dataToFile($inputData,$file){
    if(is_array($inputData)){
        foreach($inputData as $element){
            // call recursively the ‘dataToFile()’ function
            dataToFile($element,$file);
        }
    }
    else{
        if(!$fp=fopen($file,’a+’)){
            trigger_error(‘Error opening data
file’,E_USER_ERROR);
        }
        fwrite($fp,$inputData.”n”);
        fclose($fp);
    }
}

In this case, I wrote down this new recursive “dataToFile()” function, which is also handy for saving the contents of a recursive array to a specific text file. As you can appreciate, the function is a bit more compact and readable because I restructured its source code, in order to check whether a given input element is an array, and process it accordingly. In the two recursive functions defined earlier (including the one you saw in the previous section), program control is implicitly returned to the main program by the lines that save the data to the sample file:

if(!$fp=fopen($file,’a+’)){
    trigger_error(‘Error opening data file’,E_USER_ERROR);
}
fwrite($fp,$inputData.”n”);
fclose($fp);
       

After defining the above “dataToFile()” recursive function, it’s possible to set up an example that shows how to use it. Here is a simple implementation of this function:

// define recursive array
$data=array(‘element1′=>’A',’element2′=>’B',’element3′=>array
(‘recursive_element1′=>’C',’recursive_element2′=>’D',
‘recursive_element3′=>array(‘key1′=>’This is an example of
recursion’,'key2′=>’This is another example of
recursion’)),’element4′=>’E');
// call function
dataToFile($data,’data_file.txt’);

Indeed, the above example is extremely easy to grasp. Basically what I did was build up a new recursive array and use the “dataToFile()” function to save the array elements to file, which is very similar to the example you learned in the previous section.

As a result of running the previous script, below you can see how all the elements of the $data array are saved to the “data_file.txt” file:

A

B
C
D

This is an example of recursion

This is another example of recursion
E

That was pretty cool, since the “dataToFile()” function is capable of traversing a specific recursive array and storing the corresponding elements in a given text file. Now, do you see that defining a recursive function in PHP is not so difficult as it seems? I hope you do.

At this point, I coded some PHP functions that come handy for demonstrating how to use recursion in PHP. However, I’m not done yet. In the next section, I’ll write a couple of recursive functions that can be a little more helpful when they are included in real PHP applications. Thus, keep on reading to learn how this is achieved.

{mospagebreak title=Recursion in a more helpful sense: defining two handy recursive functions}

A nice conclusion for the first tutorial of this series consists of defining a pair of recursive functions that can be used in real PHP applications. The first example shows a recursive version of the PHP built-in “array_map()” function, which not surprisingly can be applied to recursive arrays, in order to escape conflictive characters. Here is the source code for the “escapeArray()” function:

function escapeArray($inputData){
   if(is_array($inputData)){
       return array_map(‘escapeArray’,$inputData);
   }
   return mysql_escape_string($inputData);
}

Despite the fact that the code for the above function is really compact, its functionality is actually worth noting. In short, all this function does is apply the “mysql_escape_string()” PHP built-in function to all the elements of a specific recursive array. This can be pretty useful in situations where a sequence of array values must be escaped before being stored in a database table.

Now, have a look at the following snippet of code, which shows how to use the above function:

// define recursive array
$data=array(“I’m Alejandro Gervasio”,array(“Take a look at some
PHP’s powerful recursive functions”,”Hey, what’s up buddy?”));
$data=array_map(‘escapeArray’,$data);
// print parsed array
print_r($data);

As you can see, after defining a recursive $data array, I used “escapeArray()” as the callback function for the PHP built-in “array_map()” function, in order to escape all the corresponding array elements. The respective output of this script is the following:

Array ( [0] => I’m Alejandro Gervasio [1] => Array ( [0] => Take
a look at some PHP’s powerful recursive functions [1] => Hey,
what’s up buddy? ) )

As illustrated above, each element of the sample array has been appropriately escaped by adding the typical leading slash to all the single quotes. Finally, the same “escapeArray()” function can be modified, in order to apply character escaping only when “magic_quotes” are disabled. Have a look at the improved version of this function:

function escapeArray($inputData){
    if(is_array($inputData)){
        return array_map(‘escapeArray’,$inputData);
   }
   if(!get_magic_quotes_gpc()){
       return mysql_escape_string($inputData);
   }
   return $inputData;
}     

In this case, the function remains nearly the same, except for the checking block that returns the escaped array elements only when the value for “magic_quotes” is turned off. Isn’t recursion a cool concept? You bet.

Final thoughts

In this first article I provided you with the basics of recursion in PHP. Through several, easy-to-grasp hands-on examples you learned how to define and use recursive functions, which can be handy for solving certain programming issues, instead of using conventional iteration.

However, this is merely the beginning of the journey. Over the next part of the series, I’ll demonstrate how to use recursion in some real object-oriented PHP applications. See you then!

Google+ Comments

Google+ Comments