Tag Archive for 'recursion vs iteration'

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:

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

//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’