By Imran


2010-04-15 21:05:31 8 Comments

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?

17 comments

@fayz 2019-01-31 11:50:43

I don't find the examples helpful either. You cant solve two problems at once when there is mathematics involved your mind is switching between two problems. Enough talking

Example:

I have a function where i am exploding strings into array based on : delimiter.

public function explodeString($string)
{
  return explode(":", $string);
}

I have another function where i am taking strings as input

public function doRec()
{
    $strings = [
        'no:go',
        'hello:world',
        'nested' => [
            'iam:good',
            'bad:array',
            'bad:how',
            'bad:about',
        ]
    ];

    $response = [];

    foreach ($strings as $string) {
        array_push($response,$this->explodeString($string));
    }

    return $response;
}

The problem is, my input has a nested array and my explodeString function recieve a type string. I can rewrite some code in explodeString function to adjust to this but i still need the same function to do the same operation on my string. Thats where i can call the method recursively within. So here is the final explodeString function with recursion.

public function explodeString($string)
{
    if (is_array($string)) {
       $combine = [];
       foreach ($string as $str) {
           array_push($combine, $this->explodeString($str));
        }
       return $combine;
    }

    return explode(":", $string);
}

@Bart 2018-03-02 07:34:31

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.

@Ales 2017-04-14 05:17:49

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.

@Joel 2015-07-20 05:35:18

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.

@Ignacio Olivieri 2017-01-07 12:51:06

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);

 ?>

@user4614642 2015-09-15 07:49:11

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. :)

@Pathros 2016-07-28 17:11:50

How do you stop it?

@user4614642 2016-08-03 12:34:10

In factorial we continously call until the argument passed is 1 and when argument is 1 we simply return 1 so stop the recursion

@user34537 2010-04-15 21:31:30

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

@Ponkadoodle 2010-04-15 22:17:34

typo... (where's your end parenthesis for the argument list of your first function?)

@Kevin 2014-07-21 06:49:29

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

@Pathros 2016-07-28 17:12:06

How do you stop it?

@Bob Ray 2014-07-04 22:16:16

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.

@Samuel 2010-04-15 21:09:05

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

@Progman 2010-04-15 21:18:04

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

@davidtbernal 2010-04-15 21:50:40

I like this answer better than the factorial one, because it's something that actually applies. How many people have to actually ever compute factorials, and why would you do factorials recursively anyway (memoization maybe, but at that point, why not just use a lookup table from the get-go).

@Imran Naqvi 2010-10-27 12:44:20

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.'--');
    }
}

@Freyr 2010-10-27 10:52:55

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.

@Anthony Forloney 2010-04-15 21:08:38

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,

@Decent Dabbler 2010-04-15 21:39:16

Although your example explains it well, the example can hardly be considered an example in laymans terms. If OP has a bit of trouble understanding recursion based on a Fibonacci example, I imagine factorials aren't gonna cut it either. Especially with these mathematical definitions involved.

@Anthony Forloney 2010-04-15 22:29:52

@fireeyedboy, stereofrog: In college, I was taught factorial function when learning recursion and it made me click. The OP and I probably have different math backgrounds, but nevertheless I omitted the factorial definition for brevity and I emphasized my laymen definition of recursion.

@Yacoby 2010-04-15 22:32:44

There is no requirement to have a end condition (base case) for a function which makes your definition slightly incorrect. (Although in PHP you have to else you end up with a stack overflow)

@James Westgate 2010-04-15 22:10:05

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.

@Shane Castle 2010-04-15 21:48:00

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.

@stacker 2010-04-15 21:46:11

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.

Related Questions

Sponsored Content

34 Answered Questions

[SOLVED] Reference - What does this error mean in PHP?

38 Answered Questions

[SOLVED] var functionName = function() {} vs function functionName() {}

23 Answered Questions

[SOLVED] Set a default parameter value for a JavaScript function

27 Answered Questions

[SOLVED] What is tail recursion?

18 Answered Questions

[SOLVED] Reference — What does this symbol mean in PHP?

24 Answered Questions

[SOLVED] What is the scope of variables in JavaScript?

20 Answered Questions

[SOLVED] What is the difference between call and apply?

15 Answered Questions

[SOLVED] Why shouldn't I use mysql_* functions in PHP?

  • 2012-10-12 13:18:39
  • Madara Uchiha
  • 203438 View
  • 2376 Score
  • 15 Answer
  • Tags:   php mysql database

9 Answered Questions

14 Answered Questions

[SOLVED] Secure hash and salt for PHP passwords

Sponsored Content