Which, from a layman's point of view, is a recursive function using PHP

Question

Can someone explain the recursive function to me in PHP (without using Fibonacci) in a layman's language and using examples? I looked at an example, but Fibonacci completely lost me!

Thanks 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:

If a function continues to call itself, how does it know when to stop? You created a condition known as the base case. Basic cases speak of our recursive call when to stop, otherwise it will loop endlessly.

Which was a good example for me, since I have strong experience in math, factorial . According to the comments below, it seems that the factorial function may be too big, I will leave it here just in case, if you want to.

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

Regarding the use of recursive functions in web development, I personally do not resort to the use of recursive calls. Not that I thought bad practice relies on recursion, but they should not be your first option. They can be fatal if not used properly.

Although I cannot compete with the sample directories, I hope this helps a bit.

(4/20/10) Update:

It would also be useful to check this question when the accepted answer demonstrates in the laity how the recursive function works. Although the OP question was about Java, the concept is the same,

• Understanding basic recursion

Answer 2

An example would be the printing of each file in any subdirectories of this directory (if you do not have symbolic links inside these directories that might somehow interrupt the function). The pseudo-code for printing all files is as follows:

 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 the auxiliary directories first, and then the files of the current directory. This idea applies to all auxiliary directories, and this is the reason for calling this function recursively for all subdirectories.

If you want to try this example, you need to check the special directories . and .. otherwise you will get hung up on calling printAllFiles(".") all the time. In addition, you should check what you need to print and what your current working directory is (see opendir() , getcwd() , ...).

Answer 3

Recursion is what is repeated. Like a function that calls itself within itself. Let me demonstrate a few pseudo-examples:

Imagine you are drinking beer with friends, but your wife is going to give you hell if you do not come home before midnight. To do this, let me create the orderAndDrinkBeer ($ time) function, where $ time is midnight minus the time needed to complete your current drink and return home.

So, having come to the bar, you order your first beer and start drinking:

 $timeToGoHome = '23'; // Let give ourselves an hour for last call and getting home function orderAndDrinkBeer($timeToGoHome) { // Let create the function that going to call itself. $beer = New Beer(); // Let 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 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 go home :( } } 

Now, let's just hope that you can’t drink enough beer to become so intoxicated that your wife will make you sleep on the couch, regardless of being at home on time. -

But yes, that's almost the way recursion goes.

Answer 4

Its a function that calls itself. This is useful for navigating to specific data structures that are repeated, such as trees. The HTML DOM is a classic example.

An example of a tree structure in javascript and a recursive function to "walk" a 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 through the tree, we call the same function repeatedly, passing the child nodes of the current node to the same function. Then we call the function again, first to the left of the node and then to the right.

In this example, we 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 to understand recursion is by passing code at runtime.

Answer 5

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

Answer 6

It is very simple when a function calls itself to perform a task for undefined and a finite amount of time. An example from my own code, a function to populate a tree with a multi-level category

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

Answer 7

Recursion is a fancy way of saying, "Do this thing again until it's done."

Two important things:

• Base case - you have a goal.
• Test - how to find out if you have where you are going.

Imagine a simple task: sort the stack of books alphabetically. A simple process will take the first two books, sort them. Now here is the recursive part: are there any more books? If so, do it again. "Repeat this again" is a recursion. “Are there more books” is a test. And “no, no more books” is a basic case.

Answer 8

The best explanation I found when I found out that I am here: http://www.elated.com/articles/php-recursive-functions/

This is because one thing:

Function when its called is created in memory (a new instance is created)

So, the recursive function DOES NOT CALL YOURSELF , but another instance calls it - therefore, more than one function in memory does some magic. Its several instances in memory that return some values ​​to themselves - and this behavior is the same when, for example, function a calls function b. You have two instances, as well as a recursive function called a new instance.

Try to draw a memory with copies on paper - this will make sense.

Answer 9

Mainly. He continues to call himself until its completion.

 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 try to execute it. Pay attention to "Did you mean" (click on it ...). http://www.google.com/search?q=recursion&spell=1

Answer 10

Recursion is an alternative to loops, it is rare that they bring more clarity or elegance to your code. A good example was given by Progman's answer, if he doesn’t use recursion, he will be forced to keep track of which directory he is currently (called state) in, recursions allow him to keep records using the stack (the area where the variables and return method address are stored )

The standard examples of factorial and Fibonacci are not useful for understanding the concept, because they are easily replaced by a loop.

Answer 11

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

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

This function is initially called to parse an object that can only contain parameters, but what if the object also contains other objects or arrays? This will need to be solved, and for the most part the basic function already does this, so the function 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, the return is a string that creates each parameter in a string by itself for readability, but you can also easily write values ​​to a log file or paste them into a database or something else.

I added the $prefix parameter to use the parent element to describe the final variable so that we can see what the value refers to. It does not include things like null values, but this can be changed from this example.

If you have an 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); 

he 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 line with 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 made nested switch statements to avoid confusion with if . . . ifelse . . . else if . . . ifelse . . . else if . . . ifelse . . . else , but it was almost as long. If this helps, just ask for the if conditional conditions, and I can insert them for those who need it.

Answer 12

A walk through a directory tree is a good example. You can do something similar to an array process. Here is a very simple recursive function that simply processes a string, a simple array of strings or a nested array of strings of any depth, replacing “hello” instances with “farewell” in the string or array values ​​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 } 

He knows when to leave, because at some point the “thing” is processing, not an array. For example, if you call replaceHello ('hello'), it will return "goodbye." If you send him an array of strings, although he will call himself once for each member of the array, then return the processed array.

Answer 13

If you add a specific value (say "1") to Anthony Forloni’s example, everything will 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 14

This is a very simple example of a factorial with recursion:

Factorials are a very simple mathematical concept. They are written as 5! and that means 5 * 4 * 3 * 2 * 1. So, 6! 720 and 4! is 24.

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

hope this is helpful to you. :)

Answer 15

This is a simple recursive (Y) example.

 <?php function factorial($y,$x) { if ($y < $x) { echo $y; } else { echo $x; factorial($y,$x+1); } } $y=10; $x=0; factorial($y,$x); ?> 

Answer 16

Recursion for Kaprekar 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 continues to call itself with the result of the calculation until it reaches the Kaprekars constant, at which it will return the number of performed calculations.

/ edit For those who do not know the Kaprekar constant, 4 digits are required, with at least two different digits.

Answer 17

I also do not find the examples useful. You cannot solve two problems at the same time, when math is involved, your mind switches between two problems. Stop talking

Example:

I have a function where I bang strings into an array based on : delimiter.

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

I have another function where I take 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 that my input has a nested array, and my explodeString function gets a string type. I can rewrite some code in the explodeString function to adapt to this, but I still need the same function to perform the same operation on my string. This is where I can call the recursively method inside. So here is the last 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); }