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:
- The calling code calls the recursive function.
- The function does any processing or calculations required.
- 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.
- 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:
- Factorials, and
- 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:
- 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. - 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 thefactorial()
function, or the outside calling code. - 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. - 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 thefactorial()
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 thefactorial()
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:
- Read the contents of the supplied folder.
- For each file in the folder, display its name.
- 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:
- 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. - Open the folder
We use the PHPopendir()
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. - Read the contents of the folder
The function then uses awhile
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 PHPis_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 functionclosedir()
, since we don’t need the directory handle any more. - Sort the filenames
Once we have our array of filenames, we call the PHPsort()
function to sort them in alphabetical order for display. - Display the filenames and process any subfolders
Finally we use aforeach
loop to work through the filenames in the array. For each filename, we display the name in anli
element, and we also check for that trailing slash to determine if the filename points to a folder. If it does, then we recursively callreadFolder()
, 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!
Not a bad article, but in my seven years of PHP programming, I probably used recursion two or three times.
Also, it is generally better to use a DirectortyIterator for directory traversals.
@v0idless: Same here, though it’s still a useful skill to know. Sometimes recursion makes much more sense than iteration.
Thanks for posting about DirectortyIterator – I didn’t know PHP had that class. Really handy!
http://php.net/manual/en/class.directoryiterator.php
Matt
Another great article! Could you show how to create and access a recursive function inside a class and return an array?
Thank you
@philatnotable: A PHP method is essentially a function so you can make recursive methods in the same way. Use $this->methodName() or ClassName::methodName() within the method if you want it to call itself.
Matt
Thanks for responding, but I have a hard time working with the resulting array. When I use a recursive function in the ‘CMS In An Afternoon’ Article class, each recursive loop adds a new dimension to the array that is returned instead of adding new items to the first array.
My results look like this:
Array ( [0] => Array ( [results] => Array ( [0] => Array ( [results] => Array ( [0] => Array ( [results] => Array ( ) ) [1] => article Object ( [name] => [entity:private] => [rx:private] => [parent] => Austrialia ) ) ) [1] => article Object ( [name] => [entity:private] => [rx:private] => [parent] => New South Wales ) ) ) [1] => article Object ( [name] => [entity:private] => [rx:private] => [parent] => Southern Highlands ) )
I’m trying to extract a list of ‘Parents’ from a mysql table with two columns; the first one is named ‘Parent’ and the other one is ‘Child’. Something like this:
———————-
Parent | Child
————————-
Austrialia | New South Wales
New South Wales | Sydney
Sydney | Port Jackson
I want ‘Port Jackson’ to return its parent (Sydney) and then for Sydney to find its parent (New South Wales) until the list runs out (Austrialia).
Thanks
@philatnotable: I can’t say for certain without seeing your entire class, but I’m guessing you might have declared your array as a local variable inside the recursive method? If so, try moving the array so it’s a static property of the class instead. That might fix it.
Thanks again Matt, but I’m still not adding each loop to the $list[] array in the $Article object.
Here’s the code:
The resulting array:
Array ( [0] => Article Object ( [parentname] => Sydney ) )
The FOREACH works, an ECHO returns this list:
Sydney, New South Wales, Australia
Thanks again
philatnotable
@philatnotable: You need to reference a static property like this:
Not:
More on static properties:
http://www.elated.com/articles/object-oriented-php-delving-deeper-into-properties-and-methods/
You can reduce one loop in your above solution for factorial by changing the following condition from:
if ( $n == 0 ) {
return 1;
}
to:
if ( $n == 1 ) {
return 1;
}