Recursive Programming

Recursion is the nemesis of many new programmers, and done improperly, the result is a slow and incorrect outcome. Done properly, very few lines of code can solve huge recursive problems. Let's take an example.

A classic example is computing factorials: 3! = 3*2*1

Lets write a function:

function factorial($number) {     
     if ($number == 1) return 1;     
     else return $number * factorial($number-1); 
}  

echo "Factorial 5 = " . factorial(5);

Example: http://backalley.net/factorial.php

The most important part of this function is the return 1 statement. Without it, you would have endless loop. This is the most common mistake for new programmers.

To create a recursive function we MUST do the following:

1. Initialize! This is often simply checking for a valid parameter. Modify this function to check for $number > 0 or return an error (-1).

2. Check for the base case. Here, if the number is 1, we return 1.

3. Redefine the answer as a set of smaller problems.

4. Run algorithm on sub-problems.

5. Combine and return the results.

Recursion is useful for mathematical functions, linked lists, array traversals, string searching, and many other more complex operations such as trees.

When you are ready to move beyond the world of simple loops, think of a recursive project and give it a shot!