Recursion
PHPWomen Contest Winner
ByPHPWomen.org recently held an article-writing contest on their Best Practices Forum. Authors of the two winning submissions each received copies of Zend Studio for Eclipse, a 1-year subscription to Linux Pro Magazine (which is called Linux Magazine outside North America), and the opportunity to feature their articles on the magazine websites. Congratulations goes to Rob Allen for his winning submission!
Recursion is the term used when an operation is repeated on the results of the same operation. That's a little confusing, but what it means to a programmer is that you have a function that calls itself.
Consider the process of adding up numbers in an array such as:
<?php
$array = array(10, 21, 4);
?>
All we need to do is iterate over the array and add each number to a variable as shown here:
<?php
function sumArray($array)
{
$total = 0;
foreach ($array as $element) {
$total += $element;
}
return $total;
}
$array = array(10, 21, 4);
$result = sumArray($array);
echo "result = $result\n";
?>
As you would expect, the output of the script is:
result = 35
But, what if the array is nested? For example, an array like this:
<?php
$array = array(10, 20, 5,
array(5, 2, 3)
);
?>
As we iterate over this new array, we will come to an element that is itself an array. We need to sum up the elements within this sub-array and, fortunately, we have just written a function that does just that (sumArray() !), so let's call it within the foreach() loop:
<?php
function sumArray($array)
{
$total = 0;
foreach ($array as $element) {
if(is_array($element)) {
$total += sumArray($element);
} else {
$total += $element;
}
}
return $total;
}
?>
This is recursion as we have called the sumArray() function from within the sumArray() function itself. That is, sumArray() is a recursive function.
We can now use our improved function to add up our nested array:
<?php
$array = array(10, 20, 5,
array(5, 2, 3)
);
$result = sumArray($array);
echo "result = $result\n";
?>
which will now output:
result = 45
As sumArray() is a recursive function, it will happily handle an array that is many nested levels deep. For example, consider an array that is nested 5 levels deep:
<?php
$array = array(10, 20, 5,
array(5, 2, 3,
array(5, 3,
array(2, 10,
array(19, 1)
),3
), 2, 7
), 3
);
$result = sumArray($array);
echo "result = $result\n";
?>
When this code is run, the output is:
result = 100
Clearly recursion is a powerful and flexible technique for solving problems involving nested data such as reading through XML structures or handling a tree within a database table (usually implemented with a parent_id column). It is also helpful when writing a sorting algorithm, but most PHP programmers don't need to do that! Recursive solutions also tend to be fairly compact and easy to debug as you only need to do it once!
Obviously, as we're programming, there are trade-offs involved! Recursive solutions are inefficient in terms of performance, so consider caching the result. Also, it's possible to get into situation where the recursion never stops. Always make sure that your function will end! Related to that, when you have deeply nested recursion, you can run out of "stack space" (this area reserved for the list of functions that are currently being called. In other words - make sure you test thoroughly :)
Go on.. write a recursive function today!
Comments
comments powered by DisqusSubscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.
-
ZorinOS 17.1 Released, Includes Improved Windows App Support
If you need or desire to run Windows applications on Linux, there's one distribution intent on making that easier for you and its new release further improves that feature.
-
Linux Market Share Surpasses 4% for the First Time
Look out Windows and macOS, Linux is on the rise and has even topped ChromeOS to become the fourth most widely used OS around the globe.
-
KDE’s Plasma 6 Officially Available
KDE’s Plasma 6.0 "Megarelease" has happened, and it's brimming with new features, polish, and performance.
-
Latest Version of Tails Unleashed
Tails 6.0 is based on Debian 12 and includes GNOME 43.
-
KDE Announces New Slimbook V with Plenty of Power and KDE’s Plasma 6
If you're a fan of KDE Plasma, you'll be thrilled to hear they've announced a new Slimbook with an AMD CPU and the latest version of KDE Plasma desktop.
-
Monthly Sponsorship Includes Early Access to elementary OS 8
If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.
All pluses and no minuses ???