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 Robert Sedgewick 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:

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?”

< ?php
class Recursion
    private $ask="<span style='font-family:sans-serif;'>Are we there yet?<br />";
    private $answer="No!<br />";
    private $counter=0;
    public function __construct()
    private function thereYet()
        //Base case (also called 'halting case')
        if($this->counter < =10)
            echo $this->ask;
            echo $this->answer;
            //Recursive call
            return $this->thereYet();
            echo "<p></p>" . $this->ask;
            $this->answer="<strong><em>Yes! We are there!</em></strong>" ;
            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 Bridge Pattern CMS

bridgeCMSA Flexible CMS

The previous post on the PHP Bridge Design pattern shows how a Bridge pattern has two connected but independent interfaces to make design flexibility for different online devices. This post explores how that same flexibility extends to making a Content Management System (CMS). Most of the Bridge participants in the design are unchanged or only slightly changed.

The major change in the Bridge design pattern actually makes it more in line with the original intention of the Bridge. The RefinedAbstraction participant (RefinedPage) no longer includes concrete content for the page. Instead, it provides the parameters for a client to add the content. This change adds flexibility and gives the developer more options than the original StandardPage class.

Two UIs and Multiple Clients

In order to make a decent CMS, you need to have at least two UIs:

  1. An Administrative UI for previewing and adding new content
  2. A User UI for viewing but not changing content

In creating the Administrative UI (HTML5/PHP/JavaScript), I had to use two PHP clients. One client is to preview the new data entered by the admin and the other client is to store the new data (after previewing and possibly editing it). Figure I provides a general overview of the UIs and the Clients that will use the Bridge pattern for a CMS:

Figure 1: User Interfaces and Clients

Figure 1: User Interfaces and Clients

The Administrative UI (BridgeCMSAdmin.html) uses the BridgeCMSAdminClient class for displaying different content and the StoreDataClient class for storing the information in a JSON file. An important condition to remember is that when using JSON files, you need to make their permissions available for reading and writing. (See the Memento II post and the special mini-post on setting permissions on Raspberry Pi systems.) Thus, the need for two clients; one for previewing new material and another for storing it in a JSON file. A lot of files are involved in this CMS; so take a look at the two different UIs and download the files for everything:

To use the Administrator Module, follow these steps in the listed order:

  1. Type in Header data, select a graphic from the drop down menu, and then type in text for the body.
  2. Click a Desktop, Tablet or Phone radio button and then click Preview Page
  3. When you have everything the way you want it, First click Transfer to Storage and next click Store Data
  4. Now click the Play button and see the page you created.

In the admin UI, I used a drop down menu with only three selections for the graphic file since only three were set up. However, it would not be difficult to upload graphics and their file names. (See the post on uploading graphics using the Template Method.)

The UIs and their Clients

The main feature in creating a CMS is the Administrative UI. It calls two different clients for dealing with previews and persistent data storage. Unless you’re planning on a fairly long body text entry, the JSON file works fine. Look at the code below, and you can see that one of the issues is that the data that is entered for the preview must be transferred to a different form. It transferring the data is a simple task with a little JavaScript. The following script is all it takes:

function transferData(formNow)
    formNow.header.value = bridgeWork.header.value;
    formNow.graphic.value = bridgeWork.graphic.value;
    formNow.bodytext.value = bridgeWork.bodytext.value;

Stored in an external JS file, it was used only when the data was going to be stored; however, before storing it, it had to be transferred from the bridgeWork form to the dataStore form.

< !DOCTYPE html>
    <link rel="stylesheet" type="text/css" href="cmsbridge.css"/>
    <script src="formXfer.js"> </script>
    <title>CMS Admin Bridge</title>
    <h2>Enter Update Data</h2>
    <form method="post" name="bridgeWork" action="BridgeCMSAdminClient.php">
        <input type="text" name="header"/>&nbsp;Header<br />
        <select name="graphic">
            <option>Select Travel Graphic</option>
            <option value="nephpAir.jpg">Air</option>
            <option value="nephpTrain.jpg">Train</option>
            <option value="nephpShip.jpg">Ship</option>
        <br />
        Enter the text for the body below:<br />
        <textarea name="bodytext" cols="48" rows="12"></textarea><p></p>
        <h3>Preview New Data</h3>
        <input type="radio" name="device" value="Desktop"/>&nbsp;Desktop<br />
        <input type="radio" name="device" value="Tablet"/>&nbsp;Tablet<br />
        <input type="radio" name="device" value="Phone"/>&nbsp;Phone<p></p>
        <input type="submit" name="deliver" value="Preview Page"/>
    <h3>Store New Data</h3>
    <form method="post" name="dataStore" action="StoreDataClient.php">
        <input type="hidden" name="header"/>
        <input type="hidden" name="graphic"/>
        <input type="hidden" name="bodytext"/>
        <button type="button" onclick="transferData(dataStore)">Transfer to Storage</button>
        <input type="submit" name="jsonstore" value="Store Data"/>

Then using build-in PHP JSON json_encode() method, the data were placed into an array and stored in the JSON file. This was done using the StoreDataClient class:

< ?php
class StoreDataClient
    private static $dataStorage=array();
    private static $jsonFile="content.json";
    //Client stores data
    public static function store()
        if (isset($_POST['jsonstore']))
    private static function setStore()
        //Pushes data from HTML to array

Just in case you’re wondering why a single PHP client class was not used for both preview and storage, it’s simple:

OOP Principle: Each class should have only a single responsibility.

We don’t want to cram classes; so each responsibility has its own class. (Click below to see the other client and the rest of the CMS.)
Continue reading ‘PHP Bridge Pattern CMS’


PHP Bridge Design Pattern

armeniaTwo Interfaces

The intent of the Bridge pattern is to decouple an abstraction from its implementation so that the two can vary independently. (GoF 151) If you don’t think about that much, it sounds like a good idea to keep an application from grinding its gears when a change is made in either the abstraction or implementation. The Freemans (Head First Design Patterns, pp. 612-613) have a great example—a universal remote control. The remote control is the abstraction and a TV set is the implementor. Concrete implementors are the different brands of TVs. As new technology arises, the remote control can be updated with new gizmos. Likewise, the TV sets can also be updated and different brands will have their own unique features. A good Bridge design will allow each to be changed without breaking the other. So far so good.

An Abstraction Has-A Implementor

About six years ago, I started looking at different Bridge design pattern examples. I ran into examples that were examples of something but did not seem to be Bridge patterns. (One was nothing more than a single interface with two different implementations. The coder explained, See, that’s a bridge. I sat there with question marks floating above my head like some cartoon character.) The GoF intent statement and Freeman example were quite clear. However, the Abstraction interface and the Implementor interface, either of which could be an abstract class or interface structure, were bridged by the abstraction having-a implementor. To fully understand a Bridge pattern, you need to understand the relationship known as a bridge between the Abstraction and Implementor participants. First, though, see what the results are by pressing the Play button and Download the files:

For an overview, take a look at Figure 1. The top half is the structure laid out by The Gang of Four—the generic class diagram for a Bridge pattern. The bottom half is the PHP implementation that addresses a common issue: Variation in the content of a Web page and the structure of a Web page. By having two interfaces, either can change independently of the other. The example shows a Web page with variable content that is displayed in desktop and mobile devices.

Figure 1: Bridge Class diagrams

Figure 1: Bridge Class diagrams

One of the important features of the Bridge pattern turns out to be quite subtle and easily overlooked.

The key method (Operation()) in the Abstraction participant is a concrete one.

In the example for this post, the IPage abstract class includes the buildPage() method. The buildPage() method uses a concrete implementation of the Implementor participant, (IDevice). You can see how the method is implemented in the IPage abstract class:

< ?php
abstract class IPage 
    abstract function doDevice(IDevice $deviceNow);
    protected function buildPage()
        echo $this->deviceSelected->buildDevice($this->header,$this->graphic,$this->body);
    protected $header, $graphic, $body, $deviceSelected;

As you can see, the abstract function doDevice() expects an IDevice object as a parameter. The $deviceSelected property is one that will be assigned a concrete Implementor (IDevice). So, in the sense that both an abstract reference using code hinting and a concrete use of an implemented IDevice are part of the IPage abstract class, it can be said to “have a” Implementor (IDevice). (Click below to see the rest of the Bridge pattern.)
Continue reading ‘PHP Bridge Design Pattern’


PHP For Academic and Practical Development: A False Dichotomy

AcademicPracticalA Dumb Argument

A few years ago Manuel Lemos wrote a post on the PHP Class blog about the wrong ideas that people have about PHP. It was largely in response to the general rejection of PHP by academics and others who hold themselves as the high priests of computing. It’s not that PHP is not taught in some universities, it’s just that getting a paper accepted at computer science conference in PHP is difficult. (By the way, Harvard University includes PHP in one of their introductory computer courses, and more than a few universities offer PHP as part of changing curricula that responds to the world around them.) Coming from academia myself, I’ve known CS faculty who act like teenage drama queens at the mention of PHP. However, I’ve also known academics who embrace PHP as they’ve come to realize that it is indeed an object oriented language and light years away from the original “Personal Home Page” intended for modest personal use. Besides, PHP is a server-side language and can communicate with an Internet-based data bases like MySQL and it’s open source.

The other side of the coin contains the legions of developers who have a job with a PHP-coded product to get out the door. They may not have a degree in computer science, or even a college degree of any sort. They have learned programming on their own and have settled on PHP as a language of choice. Generally, they also know HTML, JavaScript, CSS, MySQL and supporting Internet technologies. They see and use PHP as a practical tool to accomplish a set of goals. Their coding practices range from hacks to fully developed professional coding. Learning how to code is like learning how to write or do math; some do it well and some just enough to get by. Many such coders learn to code at work. Their job environment sets up the protocols for coding, and they follow the protocol whether they have a college degree or not. For example, one coder I know was working at a company whose new boss set up a Model View Controller (MVC) and showed everyone how to work with it. The coder learned MVC at work.

Same Goal; Different Paths

The stereotype of academics by non-academic coders is often one of fussy hair-splitters who accomplish nothing practical. The academics, on the other hand, see non-academic coders as hacks who throw together code that is a rat’s nest of statements that cannot be unraveled or re-used; they just hack out another rat’s nest. Their priorities center around an idiosyncratic and often eclectic collection of ideas, many of which are misguided or used out of context.

Both stereotypes, of course, are dead wrong. In fact, academics and practical computing have the same goals, and the goals are often from the same sources. Object oriented programming (OOP) has its origins in the practical realm of making large programming projects more manageable supported by both business and academic interests. For business, this means a more effective and efficient use of programmers’ time and the capacity to re-use the code and for programmers to work in teams that achieve a division of labor for faster development. The larger the project the more important this becomes. For academics, OOP represents a more efficient and effective programming paradigm. What’s the difference? Not much that I can see.

Different Roles: Programmers and IT Techs

suzyQprogrammerA while back my email was hacked through our university mail server. I was informed of the attack, and I had to go through the process of changing passwords and other hassles to get it fixed. The IT office sent an IT Tech up to help me get everything reset, and we got to talking shop.

Much to my surprise, he told me that he really didn’t like to program. For some reason, I simply assumed that if a person was into IT, he/she would also like to program. However, I should have known better. The most loathsome chore for me is mucking about with set-ups. When I update PHP or install a new version of MySQL, there’s a lot of tweaking that I have to do so that everything I’ve done still works. If there’re any commands I have to issue via the terminal, it depends on whether I’m working with Windows (and which version), Mac OS X (and which version) or Linux (and which flavor). Further there are PHP files (like php.ini) that must be tweaked as well. Every time I have to look up the different commands on the different OS platforms, and it differs for the language, database and what I consider the fickle whim of the person who wrote the blasted parameters in the first place. So, no, I do not like IT work or system administration.(However, I love IT Techs and System Administrators who keep everything humming along.)

Problems seem to arise when IT Techs, who are not also programmers, make pronouncements about programming. One guy I ran into who was super helpful in getting my Raspberry Pi configured with a Raspbian OS (a Linux version of Debian OS configured for the Raspberry Pi) turned into a jerk when I was helping Raspberry Pi users ease into PHP. He started mouthing off about PHP and OOP, and it was clear that he had no idea what he was talking about. He figured that since he knew how to issue short Linux commands, he was an expert on all things programming. For a newbie, these characters can cause a lot of damage because noobs probably cannot distinguish between programming and system administration. (By the same token, just because a person is a good programmer does not mean that she can help you set up the right flags and settings on your OS.)

Whether you’re an IT Tech or a programmer (or both), it’s important to realize that system administration and programming live on two different planets. I fully realize that there is some overlap, but each requires a different mindset. Good IT Techs know which terminal/OS commands to issue and the order to issue them in. Programmers, on the other hand, really work in an environment where they both create the structures and write code for the structures they create. Classes and methods along with arrays, loops, conditionals and a host of data types and properties need a different kind of orchestration. Keeping them separate is essential to excelling in both.


OOP for PHP: An Introduction & Invitation

NEClogoWho’s Afraid of Big Bad OOP?

In September (6th-7th), I’ll be giving a presentation at the NorthEast PHP & UX Conference in Boston. It’s being held at Microsoft’s New England Research & Development (NERD) Center right next to the M.I.T. campus. The past conferences have been a lot of fun and very informative, and the facilities Microsoft has built are state-of-the-art. It’s a great place for a PHP conference.

The presentation, Easing into PHP Object Oriented Programming (OOP), is designed to get PHP programmers “over the hump” between sequential/procedural programming and object oriented programming. As you will see, the hump isn’t that high and the transition is not at all difficult.

In the past on this blog, I’ve written about similar issues (No Time for OOP) and (I Was a PHP Programmer with 1 Year Experience 20 Times). So, if you’ve been thinking about upgrading your skills without any drama or unnecessary complexity, you might be interested in this great PHP conference. It would be a rare treat for me to meet some of you in person.

You can find out all about the program here: 2014 Northeast PHP Conference.