What in layman's terms is a Recursive Function using PHP

Can anyone please explain a recursive function to me in PHP (without using Fibonacci) in layman language and using examples? i was looking at an example but the Fibonacci totally lost me!

Thank you in advance ;-) Also how often do you use them in web development?

Laymens terms:

A recursive function is a function that calls itself

A bit more in depth:

If the function keeps calling itself, how does it know when to stop? You set up a condition, known as a base case. Base cases tell our recursive call when to stop, otherwise it will loop infinitely.

What was a good learning example for me, since I have a strong background in math, was factorial. By the comments below, it seems the factorial function may be a bit too much, I'll leave it here just in case you wanted it.

function fact($n) {
  if ($n === 0) { // our base case
     return 1;
  }
  else {
     return $n * fact($n-1); // <--calling itself.
  }
}

In regards to using recursive functions in web development, I do not personally resort to using recursive calls. Not that I would consider it bad practice to rely on recursion, but they shouldn't be your first option. They can be deadly if not used properly.

Although I cannot compete with the directory example, I hope this helps somewhat.

(4/20/10) Update:

It would also be helpful to check out this question, where the accepted answer demonstrates in laymen terms how a recursive function works. Even though the OP's question dealt with Java, the concept is the same,

Understanding basic recursion

An example would be to print every file in any subdirectories of a given directory (if you have no symlinks inside these directories which may break the function somehow). A pseudo-code of printing all files looks like this:

function printAllFiles($dir) {
    foreach (getAllDirectories($dir) as $f) {
        printAllFiles($f); // here is the recursive call
    }
    foreach (getAllFiles($dir) as $f) {
        echo $f;
    }
}

The idea is to print all sub directories first and then the files of the current directory. This idea get applied to all sub directories, and thats the reason for calling this function recursively for all sub directories.

If you want to try this example you have to check for the special directories . and .., otherwise you get stuck in calling printAllFiles(".") all the time. Additionally you must check what to print and what your current working directory is (see opendir(), getcwd(), ...).

Recursion is something that repeats itself. Like a function that calls itself from within itself. Let me demonstrate in a somewhat pseudo example:

Imagine you're out with your buddies drinking beer, but your wife is going to give you hell if you don't come home before midnight. For this purpose, let's create the orderAndDrinkBeer($time) function where $time is midnight minus the time it takes you to finish your current drink and get home.

So, arriving at the bar, you order your first beer and commence the drinking:

$timeToGoHome = '23';  // Let's give ourselves an hour for last call and getting home

function orderAndDrinkBeer($timeToGoHome) {  // Let's create the function that's going to call itself.
    $beer = New Beer();  // Let's grab ourselves a new beer
    $currentTime = date('G'); // Current hour in 24-hour format

    while ($beer->status != 'empty') {  // Time to commence the drinking loop
        $beer->drink();  // Take a sip or two of the beer(or chug if that's your preference)
    }

    // Now we're out of the drinking loop and ready for a new beer

    if ($currentTime < $timeToGoHome) { // BUT only if we got the time
        orderAndDrinkBeer($timeToGoHome);  // So we make the function call itself again!
    } else {  // Aw, snap!  It is time :S
        break; // Let's go home :(
    }
}

Now let's just hope you weren't able to drink enough beer to become so intoxicated that your wife is going to make you sleep on the couch regardless of being home on time -.-

But yeah, that's pretty much how recursion goes.

Its a function that calls itself. Its useful for walking certain data structures that repeat themselves, such as trees. An HTML DOM is a classic example.

An example of a tree structure in javascript and a recursive function to 'walk' the tree.

var tree = {
  id: 1,
  left: {
    id: 2,
    left: null,
    right: null
  },
  right: {
    id: 3,
    left: {
      id: 4,
      left: null,
      right: null
    },
    right: {
      id: 5,
      left: null,
      right: null
    }
  }
};

To walk the tree, we call the same function repeatedly, passing the child nodes of the current node to the same function. We then call the function again, first on the left node, and then on the right.

In this example, we'll get the maximum depth of the tree

var depth = 0;

function walkTree(node, i) {

  //Increment our depth counter and check
  i++;
  if (i > depth) depth = i;

  //call this function again for each of the branch nodes (recursion!)
  if (node.left != null) walkTree(node.left, i);
  if (node.right != null) walkTree(node.right, i);

  //Decrement our depth counter before going back up the call stack
  i--;
}

Finally we call the function

alert('Tree depth:' + walkTree(tree, 0));

A great way of understanding recursion is to step through the code at runtime.

What in layman's terms is a Recursive Function using PHP

Laymens terms:

A bit more in depth:

(4/20/10) Update:

Related

Recent Posts