Recursion

Several people have asked me for reasons to use recursion:

bengalpedigrees.com is a project I volunteer server and programming on. It is pretty standard family tree record keeping and outputting of pedigrees...

why use recursion on this?

For one, you write one display function, then a pedigree of any depth can be called by the same function with a little math to determine which row you are currently displaying to place table cells properly.

I five generation pedigree has 2+4+8+16+32 for a total of 62 cells. Who the heck wants to hand code a page of that mess?

This means that the website is capable of outputting 1 row, or ALL the rows, based on a single function and parameter! A tiny amount of code that provides quite a bit of functionality and makes for easy to maintain.

So, anyone else have another example for a good use of recursion?

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!