Archive for the 'Recursion' Category

PHP Recursion: The Fundamentals

recursionNailing 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:

  1. 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.
  2. Recursive calls to sub-problems converge to the base case. Each call must bring the values in use closer to the halting conditions.
  3. 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:
PlayDownload

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
< ?php
class Recursion
{
    private $ask="Are we there yet?
"
; private $answer="No!
"
; private $counter=0; public function __construct() { $this->thereYet(); } private function thereYet() { //Base case (also called 'halting case') if($this->counter < =10) { echo $this->ask; echo $this->answer; $this->counter++; //Recursive call return $this->thereYet(); } else { echo "

"
. $this->ask; $this->answer="Yes! We are there!" ; echo $this->answer; } } } ?>

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.)
Continue reading ‘PHP Recursion: The Fundamentals’

PHP OOP & Algorithms II: What to Use

algorithm2What Are the Guidelines?

Like just about everything else in computing, there’s a certain amount of empirical testing. More importantly, however, are the general principles derived by both empirical and mathematical calculations. In the first post on algorithms and OOP, you saw an example that showed how many operations were necessary to find “Waldo,” a name near the end of an array of over 1,000 elements. One used a straight up loop and the other a binary search algorithm. Both were pretty quick; in fact it was hard to tell the difference in speed, and without seeing the little dots, you would not have seen the number of iterations required in each algorithm. You also saw that quadratic algorithms grew at rates that can quickly reach a point where processing comes to a crawl.

A Table Guide

Table 1 is derived from the 4th Edition of Algorithms (2011, p. 187) by Robert Sedgewick and Kevin Wayne. I’ve summarized it further. (Examples in the book are all in Java.) It is a rough but useful guide, and I have found it handy for a quick look-up.

Table 1: Algorithm Order of Growth

Name Order of Growth Description Example
 constant  1 statement    2 + 7
 logarithmic  log N divide in half    binary search
 linear  N loop    find max
 linearithmic  N log N divide & conquer    mergesort
quadratic  N² double loop    check all pairs
cubic  N³ triple loop    check all triples
exponential 2N exhaustive search    check all subsets

Fortunately, most of the time our algorithms are pretty simple statements, single loops or recursive calls. All of the models in green are algorithms we should try and stick with. You should avoid the reds ones if possible.

What About Recursive Algorithms?

Those who love to profess a little knowledge like to say that recursion is slower than a loop. As indicated, we really don’t want to end up paying attention to small costs. Recursion is important, and using recursive algorithms is cost effective, especially since the difference in running time is negligible.

We often use recursive implementations of methods because they can lead to compact, elegant code that is easier to understand than a corresponding implementation that does not use recursion.
~Robert Sedgewick and Kevin Wayne

(A recursive example of a logarithmic algorithm is not included here, but you can find a recursive binary search in the post on binary searches.) What we need to pay attention to are the order-of-growth issues. For example, quadratic algorithms on the lower end of the scale are not really that bad, but when the N increases at a squaring rate, it’s easy to run into problems. So if you avoid quadratic algorithms, you’ll be better off when the N increases. On the other hand, whether you’re using a recursive method for a binary search, you’ll not see that much of a difference as the N increases compared to non-recursive methods.

A Strategy Design Pattern Handles Algorithms

This blog has lots of posts detailing the Strategy design patterns; so if you’re not familiar with a PHP implementation of the Strategy pattern, you might want to take a quick look at the code. To get started, play the example and download the code.
PlayDownload

In the last post on algorithms, the program used a Factory Method pattern to produce an array, and in this post, the same pattern is used and two additional array products have been added. However, instead of having the algorithm classes be more or less on their own, all of the algorithm classes have been organized into a Strategy design pattern. Figure 1 is a file diagram of the objects in the application:

Figure 1: Object groupings with Strategy and Factory Method patterns

Figure 1: Object groupings with Strategy and Factory Method patterns

If Figure 1 looks a bit daunting, it is only three object groupings. The HTML and PHP Client make a request for one of seven algorithm implementations through a Strategy pattern. The concrete strategy implementations all get their data from a “data factory.” Figure 2 provides an easier (and more accurate) way to understand what’s going on.

Figure 2: Overview of the main purposes of the objects.

Figure 2: Overview of the main purposes of the objects.

So instead of having a complex task, you only have three groupings of classes and interfaces: Those making a request (Clients), those executing operations on data (Algorithms) organized as a Strategy pattern and the data itself organized with a Factory Method (Data.)

Figure 2 shows a simplified version of what the program does. The Context class considerably eases the requesting process. The HTML UI passes the name of the requested concrete strategy to the Client, and the Client uses the name as a parameter in a Context method. The Client is not bound to any of the concrete strategies because the strategy classes are handled by a Context object and method. (Click continue to see the PHP implementations of the algorithms.)
Continue reading ‘PHP OOP & Algorithms II: What to Use’

PHP OOP: Back to Basics

beginBack to Basics

Whenever I venture outside of PHP, which has become more regular as I’m working on app development in both iOS and Android. The former is Objective C and the latter, Java. Both languages are embedded in OOP and design patterns. It is during these ventures abroad (so to speak) that I’m reminded of some core issues in good OOP. I usually notice them when I realize that I’m not exactly paying attention to them myself.

Don’t Have the Constructor Function Do Any Real Work

When I first came across the admonition not to have the constructor function do any real work, I was reading Miško Hevery’s article on a testability flaw due to having the constructor doing real work. More recently, I was reviewing some materials in the second edition of Head First Java, where the user is encouraged to,

Quick! Get out of main!

For some Java and lots of C programmers “main” is the name for a constructor function, but I like PHP’s __construct() function as the preferred name since it is pretty self-describing. “Main” is a terrible name because the real main is in the program made up of interacting classes.

In both cases, the warning about minimizing the work of the constructor function is to focus on true object oriented applications where you need objects talking to one another. Think of this as a series of requests where a group of people are all cooperatively working together, each from a separate (encapsulated) cubicle, to accomplish a task. By having the constructor function do very little, you’re forcing yourself (as a programmer) to use collaborative classes. Play the example and download the code to get started:
PlayDownload

A General Model for PHP OOP

As a nice simple starting place for PHP OOP, I’ve borrowed from the ASP.NET/C# relationship. ASP.NET provides the forms and UI, and C# is the engine. As an OOP jump-off point, we can substitute HTML for ASP.NET and PHP for C#. The Client class is the “requester” class. The UI (HTML) sends a request to the Client, and the Client farms out the request to the appropriate class. Figure 2 shows this simple relationship.

Figure 1: A Simple OOP PHP Model

Figure 1: A Simple OOP PHP Model

If you stop and think about it, OOP is simply a way to divide up a request into different specializations.

Avoid Conditional Statements if Possible

Figure 2: Requests begins with a UI built in HTML

Figure 2: Requests begins with a UI built in HTML

If you avoid conditional statements, and this includes switch statements, I think you can become a lot better programmer. In the example I built for this post, the user chooses from two different types of requests (classes), and each request has a refined request (method) that provides either of two different kinds of math calculations or display options. Figure 2 shows the UI (HTML) for the example. If the user selects “Do a Calculation” it sends the request to the Calculate class, but if the user selects “Display a story”, the request is handled by the Display class. Further, not only must the right class be selected, the right method in that class must be selected as well. The obvious answer is to get information from the UI and using a switch or set of conditional statements work out in the Client how to handle each request. You could even use (shudder) nested conditional statements. That approach could work, but when you start piling up conditional statements, you’re more likely to introduce errors, and when you make changes, you’re even more likely to make errors. The only good thing about conditionals is that you don’t have to tax your brain to use them.

Suppose for a second that all of your conditional statements were taken away. How, using the information sent from the HTML UI to the Client class can the selections be made without conditional statements? (Think about this for a moment.)

Think, pensez, pense, думайте, piense, 생각하십시오, denken Sie, 考えなさい, pensi, 认为, σκεφτείτε, , denk

Like all things that seem complex, the solution is pretty simple. (Aren’t they all once you know the answer.) Both classes were given the value of their class name in their respective radio button input tags. Likewise, the methods were given the value of their method names. With two radio button sets (request and method), only two values would be passed to the Client class. So all the Client had to do was to use the request string as a class name to instantiate an instance of the class, and employ the following built-in function:

call_user_func(array(object, method));

That generates a request like the following:

$myObject->myMethod;

In other words, it acts just like any other request for a class method. By coordinating the Client with the HTML UI, that was possible without using a single conditional statement. In this next section, we’ll now look at the code.
Continue reading ‘PHP OOP: Back to Basics’

PHP Recursion Using Factory Method: Programming to the Interface

recurCoverRecursion as Client

Previous posts on this blog discussed Recursion and the Factory Method design pattern. In working with a recursive object to traverse a list of strings or numbers (or any other objects for that matter), PHP developers typically target an array. In developing a simple recursive object, I realized that it made more sense to set up an another class for the array object. Why bind the process or creating and populating an array to the object designed to transverse it? After all, what if you wanted to use the object to traverse any list; not just the one bound to the recursion operation?

The Factory Method for Handling Array Objects

From the not-too-difficult decision to separate the array creation and population process from the transversal process, it was a pretty quick leap to using the Factory Method. That would give me plenty of flexibility, and I would be able to use the factory implementations to do different things with the products—like sort or filter them before returning them to the requesting client.

In this case, the requesting client would be the Recursion object.

The Client class triggers the appropriate method in the Recursion object to select whatever list is available. The selection process would be handled by an HTML UI. The class diagram is integrated into the application. Click the Play button below first to see the operation and class diagram and then the Download button to get all of the files:
PlayDownload

When you Play the program, notice in the class diagram that the Recursion class includes a method, getArray(Factory). This method is an example of programming to the interface and not the implementation. The method expects an argument that is a Factory child, but it can be any Factory implementation. The type hint is the Factory interface and so any implementation of Factory works fine. As a result, you can add as many different Factory implementations as you want without having to worry about a train wreck like you can get easily by programming to implementations.

The Recursion Class Makes use of the Factory

As noted at the outset, the Recursion object is set up to use any Factory implementation. In this example, only three implementations use the Factory interface. The factory method itself is makeArray(), but it’s left to the implementations how the array to be returned to the requester—the Recursion class. The PeopleFactory and PetsFactory sort the list in alphabetical order before returning it to the requesting client. However, the ToolsFactory uses a reverse sort so that the highest Wrench element is first and the Awl is last. The recursive iterator in the Recursion object could care less; it just transverses whatever list it gets from the Factory implementation and prints it to the screen.


class Recursion
{
    //The Recursion class is the Client
    //in making a request from the Factory
    private $members;
    private $counter=0;
    private $size;
 
    public function getPeople()
    {
        //Makes request to Factory child
        $factoryNow=new PeopleFactory();
        $this->getArray($factoryNow);
    }
 
    public function getTools()
    {
        //Makes request to Factory child
        $factoryNow=new ToolFactory();
        $this->getArray($factoryNow);
    }
 
    public function getPets()
    {
        //Makes request to Factory child
        $factoryNow=new PetsFactory();
        $this->getArray($factoryNow);
    }
 
    //By programming to the interface (Factory)
    //you can use different implementations
    private function getArray(Factory $factoryBuild)
    {
        $this->members=$factoryBuild->makeArray();
        $this->size=count($this->members)-1;
        $this->recursive();
    }
 
    private function recursive()
    {  
        if($this->counter <= $this->size)
        {
            echo "" . $this->members[$this->counter] . "
"
; ++$this->counter; return $this->recursive(); } } } ?>

As you can see, the recursive() method is pretty simple. It just keeps using echo to send the current element value to the screen, increments the counter by 1, and then if it hasn’t exceeded the length of the array, it calls itself to repeat the process. The Factory implementations already took care of the sorting arrangements–or anything else developers want the Factory implementations to do.

Each of the 3 public “getter” methods call the private getArray(Factory) method using a Factory implementation as an argument. The passed argument calls the factory method (makeArray()) to get the requested array which is stored in the $members property. Finally, getArray(Factory) calls the recursive() iteration method that traverses the $members property containing the array.

A Lot of Work for Iteration

If you’re thinking

…that’s a lot of work for a simple operation (displaying sorted lists on the screen)

I’d not disagree. The point of design patterns, though, is re-use on a much larger scale. As projects get bigger and bigger, you need tools to deal with them. The good news is that if you can use them on a small scale like the examples on this blog and in Learning PHP Design Patterns, you’re prepared to work on larger projects involving teams of programmers and some seriously good applications.