PHP Recursive Functions: How to Write Them, and Why They’re Useful

Like most programming languages that support functions, PHP lets you write recursive functions. In this tutorial, we’ll explore the concept of recursion in PHP, and discover how to create recursive functions for various tasks.

Recursion is one of those topics that can seem confusing at first, but once you start writing recursive functions you’ll see how elegant recursion can be!

What is recursion?

Broadly speaking, recursion occurs when something contains, or uses, a similar version of itself. That similar version then contains or uses another similar version of itself, and so on. Sometimes this process can go on forever, such as when you hold 2 mirrors directly opposite each other, creating an infinite series of reflections. More often, though, the number of repetitions, or “depth” of the recursion, is limited by some sort of end condition.

Recursion occurs in all sorts of everyday situations. For example, many artists have created recursive pictures, where the picture contains a smaller version of itself; that smaller version then contains another smaller version, and so on. A famous example of this is the picture on the Droste cocoa tin:

Geek note: I produced the image at the top of this article by calling my MacBook from my iPhone using FaceTime, then pointing the phone camera at the MacBook’s screen, creating feedback. A classic example of recursion if ever there was one!

Recursion in computing

When talking specifically about computer programming, recursion occurs when a function calls itself. There’s nearly always an end condition of some sort — known as the base case — otherwise the function would continue to call itself indefinitely (or at least until the computer ran out of memory).

Recursion can be thought of as an alternative to iteration — that is, while and for loops. Some problems are better suited to recursion, while others are easier to do with iteration. Often you can use either recursion or iteration to solve a particular problem.

How to write a recursive function in PHP

In general terms, a recursive function works like this:

1. The calling code calls the recursive function.
2. The function does any processing or calculations required.
3. If the base case has not yet been reached, the function calls itself to continue the recursion. This creates a new instance of the function.
4. If the base case is reached, the function just returns control to the code that called it, thereby ending the recursion.

In pseudocode, a simple recursive function looks something like this:

function myRecursiveFunction() {

  // (do the required processing...)

  if ( baseCaseReached ) {

    // end the recursion
    return;

  } else {

    // continue the recursion
    myRecursiveFunction();
}

The best way to understand recursive functions is to look at some practical examples. Let’s explore 2 complete PHP examples that show how recursion works:

1. Factorials, and
2. Reading a tree of files and folders

Example 1: Factorials

If you remember your high school maths, a factorial of a given number is the product of all positive integers between 1 and the number (inclusive). For example:

5! = 5 x 4 x 3 x 2 x 1 = 120

Let’s write a recursive function to calculate the factorial for a given number, n:

<?php

function factorial( $n ) {

  // Base case
  if ( $n == 0 ) {
    echo "Base case: $n = 0. Returning 1...<br>";
    return 1;
  }

  // Recursion
  echo "$n = $n: Computing $n * factorial( " . ($n-1) . " )...<br>";
  $result = ( $n * factorial( $n-1 ) );
  echo "Result of $n * factorial( " . ($n-1) . " ) = $result. Returning $result...<br>";
  return $result;
}

echo "The factorial of 5 is: " . factorial( 5 );

?>

As you can see, this function is pretty simple. Let’s break it down:

1. Begin the function

   function factorial( $n ) {
   

   First we define the function, factorial(), and include a parameter, $n, to hold the number that we want to calculate the factorial for.

2. Set up the base case

     // Base case
     if ( $n == 0 ) {
       echo "Base case: $n = 0. Returning 1...<br>";
       return 1;
     }
   

   Within our function, we first define the base case, which is when the supplied value, $n, equals 0. If this is the case then we’ve reached the end of our recursion, and we simply return 1 (the factorial of 0 is 1). This value is returned to the code that called it, which will be either another instance of the factorial() function, or the outside calling code.

3. Do the recursion

     // Recursion
     echo "$n = $n: Computing $n * factorial( " . ($n-1) . " )...<br>";
     $result = ( $n * factorial( $n-1 ) );
     echo "Result of $n * factorial( " . ($n-1) . " ) = $result. Returning $result...<br>";
     return $result;
   }
   

   The last block of code in the function performs the actual recursion, and it’s run as long as $n is greater than zero. It calls itself, passing in $n-1 as the argument, and multiplies the resulting value by $n. In other words, it computes the factorial of the integer that is 1 less than the current value, then multiplies this by the current value to get the current value’s factorial. It then stores this value in $result and returns it to the calling code.

4. Test the function

   echo "The factorial of 5 is: " . factorial( 5 );
   

   Finally, we test our function by calling it with a value of 5. This produces the correct result (120).

I’ve added some echo statements to the function to make it clearer what’s going on. Try it out by clicking the button below:

Here’s the output:

$n = 5: Computing 5 * factorial( 4 )...
$n = 4: Computing 4 * factorial( 3 )...
$n = 3: Computing 3 * factorial( 2 )...
$n = 2: Computing 2 * factorial( 1 )...
$n = 1: Computing 1 * factorial( 0 )...
$n = 0: Base case. Returning 1...
$n = 1: Result of 1 * factorial( 0 ) = 1. Returning 1...
$n = 2: Result of 2 * factorial( 1 ) = 2. Returning 2...
$n = 3: Result of 3 * factorial( 2 ) = 6. Returning 6...
$n = 4: Result of 4 * factorial( 3 ) = 24. Returning 24...
$n = 5: Result of 5 * factorial( 4 ) = 120. Returning 120...
The factorial of 5 is: 120

The echo statements let you see how the recursive function actually runs:

• The first time around, $n = 5. This doesn’t trigger the base case, so the function calls itself recursively to derive the factorial of 5 from the factorial of 4 ("Computing 5 * factorial( 4 )"). This creates a new instance of the factorial() function. As when calling any function in PHP, the first instance of the function is “frozen” while the new instance of the function runs.
• This new instance of the function ($n = 4) repeats the process, calling the factorial() function again to derive the factorial of 4 from the factorial of 3 ("Computing 4 * factorial( 3 )").
• This “nested calling” process continues as long as $n is not zero. Each time an instance of the function calls a new instance, the first instance is “frozen” until the second instance of the function finishes and returns a value (we’ll see this happen in the next steps).
• When $n is zero, the base case is reached. The function returns 1 to its calling code, without calling itself.
• This returning action “unfreezes” the instance of the function that called it ($n = 1), which then accepts the return value, uses it to compute and display the result ("Result of 1 * factorial( 0 ) = 1"), and also returns this computed factorial back up to the function that called it ($n = 2).
• This process repeats itself back up the chain, until the topmost function ($n = 5) returns the value (120) to the outside calling code.

This process of freezing instances of the factorial() function as they call new instances explains why the output shows all the “Computing…” lines first, followed by the base case, followed by the “Result of…” lines in reverse order as the nested instances start returning values back up the chain.

Want the nitty-gritty? This “freezing” of functions is done automatically by the PHP engine using what is known as a call stack. When a function calls another function, the calling function’s state is pushed onto the top of the call stack (much like adding a card on top of a deck of cards). When the called function returns, the calling function’s state is taken off the top of the stack, and the function continues running where it left off.

Example 2: Reading a tree of files and folders

The factorial example above is fairly straightforward, but it’s a bit — shall we say — theoretical. Let’s look at a really practical use for recursion: reading a directory structure on a hard drive, and displaying a list of the files and folders in the structure.

Typically a folder contains one or more files and/or subfolders. Each subfolder may itself contain more files and subfolders, and so on. This tree-like nature of a file system makes it a perfect fit for recursion.

Our folder-reading function needs to work like this:

1. Read the contents of the supplied folder.
2. For each file in the folder, display its name.
3. If a subfolder is found in the folder, display its name, then call the function recursively to read the contents of the subfolder, and so on.

Here’s our complete script:

<!doctype html>
<html lang="en">
<head>
<title>Recursion Example #2: Reading a Tree of Files and Folders</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
</head>
<body>

<h1>Recursion Example #2: Reading a Tree of Files and Folders</h1>

<?php

$folderPath = "photos";

function readFolder( $path ) {

  // Open the folder
  if ( !( $dir = opendir( $path ) ) ) die( "Can't open $path" );
  $filenames = array();

  // Read the contents of the folder, ignoring '.' and '..', and
  // appending '/' to any subfolder names. Add all the files and
  // subfolders to the $filenames array.

  while ( $filename = readdir( $dir ) ) {
    if ( $filename != '.' && $filename != '..' ) {
      if ( is_dir( "$path/$filename" ) ) $filename .= '/';
      $filenames[] = $filename;
    }
  }

  closedir ( $dir );

  // Sort the filenames in alphabetical order
  sort( $filenames );

  // Display the filenames, and process any subfolders

  echo "<ul>";

  foreach ( $filenames as $filename ) {
    echo "<li>$filename";
    if ( substr( $filename, -1 ) == '/' ) readFolder( "$path/" . substr( $filename, 0, -1 ) );
    echo "</li>";
  }

  echo "</ul>";
}

echo "<h2>Contents of '$folderPath':</h2>";
readFolder( $folderPath );

?>

</body>
</html>

I’ve created a demo based on the above script, using some photos in various folders and subfolders. You can see the result by clicking the button below:

Let’s work through the readFolder() function to see how it does its stuff:

1. Begin the function
   We define the function, readFolder(), and include a parameter, $path, that will contain the path to the folder we want to read.
2. Open the folder
   We use the PHP opendir() function to open the folder for reading, and create a new array called $filenames to store the names of any files and subfolders that we find inside the folder.
3. Read the contents of the folder
   The function then uses a while loop to read each item inside the folder. The entries '.' (current folder) and '..' (parent folder) are skipped. If the item is a folder — which we determine by calling the PHP is_dir() function — then we append a '/' to the end of the filename. This lets the user know that it’s a folder, and we’ll also look for this slash later in the function to determine if the item was a folder or a file. Finally, we append each item’s filename to the $filenames array.

   When we’re done with the while loop, we close the directory by calling the PHP function closedir(), since we don’t need the directory handle any more.

4. Sort the filenames
   Once we have our array of filenames, we call the PHP sort() function to sort them in alphabetical order for display.
5. Display the filenames and process any subfolders
   Finally we use a foreach loop to work through the filenames in the array. For each filename, we display the name in an li element, and we also check for that trailing slash to determine if the filename points to a folder. If it does, then we recursively call readFolder(), passing in the path to the folder. In this way, our function recursively works its way through all the folders in the tree, displaying the contents of each folder as it goes.

Once we’ve created our recursive readFolder() function, we just need to store the path to the top-level folder that we want to read in $folderPath, then call readFolder() with this path to begin the process. In this case, I’ve specified a path of "photos", which reads the subfolder called "photos" in the same folder as the script.

Unlike the factorial() example earlier — where each instance of the function calls itself only once — the readFolder() function might call itself several times throughout its foreach loop if there are several subfolders in the current folder. You can imagine the instances of the function creating a tree-like structure, mirroring the folder structure on the hard drive.

The base case in this example occurs when there are no subfolders in the current folder. At that point, that instance of the function doesn’t call itself any more. When the end of the function is reached, the function automatically returns control to the function that called it. Eventually, control percolates back up to the top of the “tree”, and the script exits.

Summary

In this tutorial you’ve explored the concept of recursion, and learned how to write recursive functions in PHP. You’ve:

• Learned about recursion in everyday life
• Seen how recursion works in programming terms, and how base cases work
• Discovered how to write a recursive function
• Created a recursive function to calculate factorials
• Seen how recursive functions actually run, and
• Written a recursive script that displays all the files and subfolders inside a folder on the hard drive.

If you’d like to see more examples of recursive functions, check out Wikipedia’s page on recursion.

As you’ve seen, recursion can be a very useful tool for solving certain types of problem. While you’re unlikely to use recursion much in day-to-day PHP programming, you’ll find this skill invaluable for those times when you really do need a recursive function!

Recursion can be tricky to get your head around at first, but I hope that this tutorial has made the concept a little clearer. Once you’ve written a few recursive functions of your own then you should find it plain sailing.

Thanks for reading, and happy coding!