What is a RECURSIVE Function in PHP?

Question

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?

Answer 1

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

Answer 2

Simple put: A recursive function is a function that calls itself.

Answer 3

Or lets say you are looking after a specific file and you just know that somewhere under this path its located. So you have a function which could look like this:

searchFile($folder, $filename)

Then you go recursivly from top to down through all the folders and compare all the files. If you have scannend all files but it wasnt there, you just call again the searchFile function with the new directory and so on.

Web Development Example:

Maybe a typical web development example would be a gallery script. It searches recursivly a given folder after ".jpg" or ".png" and adds the paths to an array.

Answer 4

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(), ...).

Answer 5

Recursion. See "Recursion."

Answer 6

Basically this. It keeps calling itself until its done

void print_folder(string root
{
    Console.WriteLine(root);
    foreach(var folder in Directory.GetDirectories(root))
    {
        print_folder(folder);
    }
}

Also works with loops!

void pretend_loop(int c)
{
    if(c==0) return;
    print "hi";
    pretend_loop(c-);
}

You can also trying googling it. Note the "Did you mean" (click on it...). http://www.google.com/search?q=recursion&spell=1

Answer 7

Recursion is an alternative to loops, it's quite seldom that they bring more clearness or elegance to your code. A good example was given by Progman's answer, if he wouldn't use recursion he would be forced to keep track in which directory he is currently (this is called state) recursions allows him to do the bookkeeping using the stack (the area where variables and return adress of a method are stored)

The standard examples factorial and Fibonacci are not useful for understanding the concept because they're easy to replace by a loop.

Answer 8

Recursion is a fancy way of saying "Do this thing again until its done".

Two important things to have:

1. A base case - You've got a goal to get to.
2. A test - How to know if you've got to where you're going.

Imagine a simple task: Sort a stack of books alphabetically. A simple process would be take the first two books, sort them. Now, here comes the recursive part: Are there more books? If so, do it again. The "do it again" is the recursion. The "are there any more books" is the test. And "no, no more books" is the base case.

Answer 9

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.

    1
   / \
  2   3
     / \
    4   5

--

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.

Answer 10

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.

Answer 11

It is very simple, when a function calls itself for accomplishing a task for undefined and finite number of time. An example from my own code, function for populating a with multilevel category tree

function category_tree($parent=0,$sep='')
{
    $q="select id,name from categorye where parent_id=".$parent;
    $rs=mysql_query($q);
    while($rd=mysql_fetch_object($rs))
    {
        echo('id.'">'.$sep.$rd->name.'');
        category_tree($rd->id,$sep.'--');
    }
}