What in layman's terms is a Recursive Function

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

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 2

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 3

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.

Answer 4

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.

Answer 5

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.
  }
}

Answer 6

It work a simple example recursive (Y)

<?php 


function factorial($y,$x) { 

    if ($y < $x) { 
        echo $y; 
    } else { 
        echo $x; 
        factorial($y,$x+1);
    } 
}

$y=10;

$x=0;
factorial($y,$x);

 ?>