Nailing Down Recursion
On more than one occasion on this blog, I’ve wandered off into the land of operations to examine recursion. In looking over past recursion posts and recursion discussions on the Web, I found a lot of bad information, partial information and helpful information. Likewise, I consulted some programming books, especially Robert Sedgewick’s and Kevin Wayne’s 2011 edition (4th) of Algorithms. Also, I found a great and detailed article on recursion by David Matuszek. Robert Sedgewick and Kevin Wayne are professors at Princeton and David Matuszek is a professor at the University of Pennsylvania. Not surprisingly, their focus is on larger conceptual and mathematical issues surrounding computer programming and the role that recursion plays in that context.
However, I also wanted to get a non-academic view from developers, and I found two very good posts on Martin Fowler’s Refactoring site by Dave Whipp and Ivan Mitrovic. For those of you not familiar with Martin Fowler, he’s written books and articles on computing and is one of the founders of the Agile Movement in program development. He is a primary consultant to businesses and institutions who want to optimize their programs for efficiency and effectiveness. Among PHP developers the Agile approach to programming is quite popular.
What is Recursion?
In a nutshell,
Recursion in computer programming occurs when a method calls itself.
While that definition is a starting point, a more detailed and useful one is provided by Sedewick and Wayne. They spell out three features in a good recursive method:
- A recursion begins with a conditional statement with a return. This is called the base case (or halting case), and it supplies the criterion which will stop the recursive operation.
- Recursive calls to sub-problems converge to the base case. Each call must bring the values in use closer to the halting conditions.
- Called sub-problems should not overlap.
You can find a lot of discussions and debate about the definition and use of recursive methods in programming, but the fundamental fact remains that recursion is one of the central ideas in computer science. As a professional programmer, you need to know about recursion and you should use it. This does not mean you have to use it all the time, but you need to understand what you can do with it and its limitations and advantages. Start off with the following implementations and download the code:
In PHP and other computer programs, recursion and the need for it arise all the time. So you should have some sense of how to use it and when. Like other computing concepts, you may not use it all the time, but when you need it, you really need it.
World’s Easiest Recursive Function
To get started we’ll look at a simple recursive call. It is a version of what kids do when you take them on a trip. (And what you did when you were a kid on a trip…) You’d ask the reasonable question,
Are we there yet?
If you kept calling the same query as soon as you’d received a negative response, it has recursive-like qualities. The “No!” is the base case, and the car moving to the objective (“there”) is the change that occurs between each call to the query, “Are we there yet?”
//Recursion.php class Recursion { private $ask="Are we there yet? |
The return value calls for a recursive event inside the thereYet() method. With each call, the counter variable’s value moves toward convergence with the base case. After 10 calls, the counter variable exceeds the base case and no more self-calls are made by the thereYet() method.
While that example could be handled by iteration in a loop; it provides another way to accomplish a task. It’s easy to understand and meets the criteria set up for recursion. (Click below to see more.)
Another simple example uses a slightly different way to move the main body of the recursive method to convergence with the base case. If you’ve ever visited a casino (including online casinos), you may
class Sucker
{
private $stake=1000;
public function __construct()
{
$this->doSlots();
}
//Recursive operation
private function doSlots()
{
//Base
if($this->stake >= 500)
{
//Move toward base
$this->stake=.97 * $this->stake;
echo "Your stake is now $" . round($this->stake,2) . "
|
When casinos advertise “97%” slots; they don’t mean that you will win 97% of the time, but instead that 97% is the percent of 100% you get to keep. This little recursion shows how that quickly that 97% can burn through a $1,000 stake, and converge on the base case which is half your original stake. (I couldn’t write an example that would leave you broke, but the casinos can.)
More Complex Recursive Methods
As you can see, writing a recursive method isn’t rocket science. However, you can have far more complex ones, and one of the best is the recursive binary search algorithm. Some languages, like Java, have built-in binary search methods, and this one is based on a hand-made Java program from Robert Sedgewick’s and Kevin Wayne’s Algorithms book. (By the way, it wasn’t until 2006 that someone noticed that the built-in Java binary search method had a flaw in it.)
class RecursiveBinary
{
private $phpWords;
private $search="searching...
|
This is not the first implementation of a recursive binary search method on this blog, but I think it is the best. The first thing to notice is that under two different conditions that method calls itself—when the compared value is higher or lower than the search value in a sorted list.
The base case in the binary search is really a “not found” one. As the higher gets lower and the lower gets higher (converging like the jaws of a vice), if the search term ($key) is not matched, the low will be equal to or even higher than the high value and/or vice versa. In other words, they “passed” each other like an elevator on the top floor going down and an elevator on the ground floor going up.
When You to use Recursion?
Actually, you never have to use recursive methods, but if you know recursion, you’re likely to find a situation where you can pull recursion out of your programmer’s tool box and solve a problem. Recursive methods are usually compared to loops (iteration), and fights abound over using one or the other. Some newer functional programming languages do not include loop structures, but instead rely on recursion; so obviously, you’ll have to use recursion in functional programs.
David Matuszek has some useful guidelines for using recursion, and two apply to programming in PHP.
- When processing recursively defined defined data structures. For example, when working with tree structures and algebraic data types, recursion is both easier and clearer.
- When you have nested structures. Nested loops are insane to understand and when you start generating quadratic and cubic algorithmic structures, you’re in trouble. So the next time you’re thinking of a nested loop or conditional, see if you can use a recursive method instead.
The best way to learn how to use recursive methods is to start playing with them. Instead of an iterative structure, try a recursive method, just for the fun of it.
When to use a Loop instead of Recursion?
My favorite PHP loop has always been the foreach loop. With it, I can iterate through an object and find all of its properties’ values. When creating a more generic method for dealing with any PHP object, the foreach loop will take care of business even if you don’t know the current object’s properties. For example, consider the following pair of classes:
//ObjectHouse.php class ObjectHouse { public $alpha; public $beta; public $gamma; public $delta; public function setProperties() { $this->alpha=10; //numeric value $this->beta=10 +7;//numeric expression $this->gamma="Sunny day!";//string $this->delta=true; //Boolean } } ?> //PropertyViewer.php class PropertyViewer { public function __construct() { $objectHouse=new ObjectHouse(); $objectHouse->setProperties(); echo "Property values of ObjectHouse object:"; //Iteration through unknown set of properties foreach($objectHouse as $key) { if($key==1){ $key="True";} echo "$key". " |
The ObjectHouse class is simply a general example of an object with properties. The PropertyViewer class is equally general, and with the foreach loop, it can iterate through as many or few properties as the object contains.
The foreach loop has its own elegant structure, and while I generally prefer to build my own recursive methods, when a loop will solve the problem, I’ll use a loop. If I run across a better technique using recursion, I’ll use it.
The Practicality of Recursion and Iteration
Past posts on this blog have examined iteration in detail in the context of a design pattern, and several examples have used loop structures in classes and methods. Likewise, recursion is no stranger to this blog either. Any professional programmer is familiar with and uses both. I cannot understand the heated debates that some get into over using loops and iteration instead of recursive methods. Both can be useful and so why debate their use? It’s like arguing whether the letter ‘A’ in the alphabet is better or worse than the letter ‘B.’ The letter ‘A’ is more useful in ‘apple’ and the letter ‘B’ is more useful in ‘bunny.’ Both are used in the word, ‘bear’ and neither in ‘fish.’ The same is true with recursion and loops; sometimes you use one and sometimes the other. On some occasions you may find both are required and in others, neither. However, whatever you do, don’t ignore one in favor of the other, and definitely, understand how to use both. Professional PHP programming requires both.
Copyright © 2014 William Sanders. All Rights Reserved.
0 Responses to “PHP Recursion: The Fundamentals”