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.

    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.

Simply put: a recursive function is a function that calls itself.

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(''.$sep.$rd->name.''); category_tree($rd->id,$sep.'--'); } }

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.

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.

Best explanation I have found when I was learning that myself is here:http://www.elated.com/articles/php-recursive-functions/

Its because one thing:

The function when its called is created in memory (new instance is created)

So the recursive function IS NOT CALLLING ITSELF, but its calling other instance - so its not one function in memory doing some magic. Its couple of instances in memory which are returning themselves some values - and this behavior is the same when for example function a is calling function b. You have two instances as well as if recursive function called new instance of itself.

Try draw memory with instances on paper - it will make sense.

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

Walking through a directory tree is a good example. You can do something similar to process an array. Here is a really simple recursive function that simply processes a string, a simple array of strings, or a nested array of strings of any depth, replacing instances of 'hello' with 'goodbye' in the string or the values of the array or any sub-array:

function replaceHello($a) {
    if (! is_array($a)) {
        $a = str_replace('hello', 'goodbye', $a);
    } else {
        foreach($a as $key => $value) {
            $a[$key] = replaceHello($value);
        }
    }
    return $a
}

It knows when to quit because at some point, the "thing" it is processing is not an array. For example, if you call replaceHello('hello'), it will return 'goodbye'. If you send it an array of strings, though it will call itself once for every member of the array, then return the processed array.

If you add a certain value (say, "1") to Anthony Forloney's example, everything would be clear:

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

original:

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

Here is a practical example (there are several good ones already). I just wanted to add one that is useful to almost any developer.

At some point, developers will need to parse an object as with a response from an API or some type of object or array.

This function is initially called to parse an object which may just contain parameters, but what if the object also contains other objects or arrays? This will need to be addressed, and for the most part the basic function already does this, so the function just calls itself again (after confirming that the key or value is either an object or an array) and parses this new object or array. Ultimately what is returned is a string that creates each parameter on a line by itself for readability, but you could just as easily log the values to a log file or insert into a DB or whatever.

I added the $prefix parameter to use the parent element to help describe the end variable so that we can see what the value pertains to. It doesn't include things like null values, but this can be amended from this example.

If you have the object:

$apiReturn = new stdClass();
$apiReturn->shippingInfo = new stdClass();
$apiReturn->shippingInfo->fName = "Bill";
$apiReturn->shippingInfo->lName = "Test";
$apiReturn->shippingInfo->address1 = "22 S. Deleware St.";
$apiReturn->shippingInfo->city = "Chandler";
$apiReturn->shippingInfo->state = "AZ";
$apiReturn->shippingInfo->zip = 85225;
$apiReturn->phone = "602-312-4455";
$apiReturn->transactionDetails = array(
    "totalAmt" => "100.00",
     "currency" => "USD",
     "tax" => "5.00",
     "shipping" => "5.00"
);
$apiReturn->item = new stdClass();
$apiReturn->item->name = "T-shirt";
$apiReturn->item->color = "blue";
$apiReturn->item->itemQty = 1;

and use:

var_dump($apiReturn);

it will return:

>object(stdClass)#1 (4) { ["shippingInfo"]=> object(stdClass)#2 (6) { ["fName"]=> string(4) "Bill" ["lName"]=> string(4) "Test" ["address1"]=> string(18) "22 S. Deleware St." ["city"]=> string(8) "Chandler" ["state"]=> string(2) "AZ" ["zip"]=> int(85225) } ["phone"]=> string(12) "602-312-4455" ["transactionDetails"]=> array(4) { ["totalAmt"]=> string(6) "100.00" ["currency"]=> string(3) "USD" ["tax"]=> string(4) "5.00" ["shipping"]=> string(4) "5.00" } ["item"]=> object(stdClass)#3 (3) { ["name"]=> string(7) "T-shirt" ["color"]=> string(4) "blue" ["itemQty"]=> int(1) } }

and here is the code to parse it into a string with a line break for each parameter:

function parseObj($obj, $prefix = ''){
    $stringRtrn = '';
    foreach($obj as $key=>$value){
        if($prefix){
            switch ($key) {
                case is_array($key):
                    foreach($key as $k=>$v){
                        $stringRtrn .= parseObj($key, $obj);
                    }
                    break;
                case is_object($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        default:
                            $stringRtrn .= $prefix ."_". $key ." = ". $value ."<br>";
                            break;
                    }
                    break;
            }
        } else { // end if($prefix)
            switch($key){
                case is_array($key):
                    $stringRtrn .= parseObj($key, $obj);
                    break;
                case is_object($key):

                    $stringRtrn .= parseObj($key, $obj);
                    break;
                default:
                    switch ($value) {
                        case is_array($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;
                        case is_object($value):
                            $stringRtrn .= parseObj($value, $key);
                            break;                      
                        default:
                            $stringRtrn .= $key ." = ". $value ."<br>";
                            break;
                    } // end inner switch 
            } // end outer switch
        } // end else
    } // end foreach($obj as $key=>$value)
    return $stringRtrn;
} // END parseObj()

This will return the object as follows:

shippingInfo_fName = Bill
shippingInfo_lName = Test
shippingInfo_address1 = 22 S. Deleware St.
shippingInfo_city = Chandler
shippingInfo_state = AZ
shippingInfo_zip = 85225
phone = 602-312-4455
transactionDetails_totalAmt = 100.00
transactionDetails_currency = USD
transactionDetails_tax = 5.00
transactionDetails_shipping = 5.00
item_name = T-shirt
item_color = blue
item_itemQty = 1

I did the nested switch statements to avoid confusion with if . . . ifelse . . . else, but it was almost as long. If it helps, just ask for the if conditionals and I can paste them for those who need it.

This is a very simple example of factorial with Recursion:

Factorials are a very easy maths concept. They are written like 5! and this means 5 * 4 * 3 * 2 * 1. So 6! is 720 and 4! is 24.

function factorial($number) { 

    if ($number < 2) { 
        return 1; 
    } else { 
        return ($number * factorial($number-1)); 
    } 
}

hope this is usefull for you. :)

It work a simple example recursive (Y) >
>
> function factorial($y,$x) { >
> if ($y < $x) { > echo $y; > } else { > echo $x; > factorial($y,$x+1); > } > } >
> $y=10; >
> $x=0; > factorial($y,$x); >
> ?>

Recursion used for Kaprekar's constant

function KaprekarsConstant($num, $count = 1) {
    $input = str_split($num);
    sort($input);

    $ascendingInput  = implode($input);
    $descendingInput = implode(array_reverse($input));

    $result = $ascendingInput > $descendingInput 
        ? $ascendingInput - $descendingInput 
        : $descendingInput - $ascendingInput;

    if ($result != 6174) {
        return KaprekarsConstant(sprintf('%04d', $result), $count + 1);
    }

    return $count;

}

The function keeps calling itself with the result of the calculation until it reaches Kaprekars constant, at which it will return the amount of times the calculations was made.

/edit For anyone that doesn't know Kaprekars Constant, it needs an input of 4 digits with at least two distinct digits.

> Recursion occurs when something contains, or uses, a similar version > of itself.When talking specifically about computer programming, > recursion occurs when a function calls itself.

The following link helps me to understand recursion better, even I consider this is the best so far what I've learned.

It comes with an example to understand how the inner(recursive) functions called while executing.

Please go through the article and I have pasted the test program in case if the article got trashed. You may please run the program in local server to see it in action.

https://www.elated.com/php-recursive-functions/

<?php

function factorial( $n ) {

  // Base case
  if ( $n == 0 ) {
    echo "Base case: $n = 0. Returning 1...<br>";
    return 1;
  }

  // Recursion
  echo "$n = $n: Computing $n * factorial( " . ($n-1) . " )...<br>";
  $result = ( $n * factorial( $n-1 ) );
  echo "Result of $n * factorial( " . ($n-1) . " ) = $result. Returning $result...<br>";
  return $result;
}

echo "The factorial of 5 is: " . factorial( 5 );

?>