用外行的话来说是什么是使用 PHP 的递归函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2648968/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What in layman's terms is a Recursive Function using PHP
提问by Imran
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!
任何人都可以用外行语言和示例在 PHP 中向我解释递归函数（不使用斐波那契）吗？我正在看一个例子，但斐波那契完全失去了我！
Thank you in advance ;-) Also how often do you use them in web development?
在此先感谢您 ;-) 另外，您在 Web 开发中使用它们的频率如何？
回答by Anthony Forloney
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.
因为我有很强的数学背景，所以对我来说是一个很好的学习例子是factorial。根据下面的评论，阶乘函数似乎有点太多了，我会把它留在这里以防万一。
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.
关于在 Web 开发中使用递归函数，我个人并不使用递归调用。并不是说我认为依赖递归是不好的做法，但它们不应该是您的第一选择。如果使用不当，它们可能是致命的。
Although I cannot compete with the directory example, I hope this helps somewhat.
虽然我无法与目录示例竞争，但我希望这会有所帮助。
(4/20/10) Update:
(4/20/10) 更新：
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,
检查这个问题也会有帮助，其中接受的答案以外行的方式展示了递归函数的工作原理。尽管 OP 的问题涉及 Java，但概念是相同的，
回答by Progman
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(), ...).
如果你想尝试这个例子，你必须检查特殊目录.和..，否则你会一直卡在调用中printAllFiles(".")。此外，您必须检查要打印的内容以及您当前的工作目录是什么（请参阅opendir()、getcwd()、 ...）。
回答by Freyr
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.
想象一下，你和你的朋友出去喝啤酒，但如果你在午夜之前不回家，你的妻子会让你生不如死。为此，让我们创建 orderAndDrinkBeer($time) 函数，其中 $time 是午夜减去您喝完当前饮料并回家所需的时间。
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.
但是，是的，这就是递归的方式。
回答by James Westgate
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.
它是一个调用自身的函数。它对于遍历某些重复的数据结构很有用，例如树。HTML DOM 就是一个经典的例子。
An example of a tree structure in javascript and a recursive function to 'walk' the tree.
javascript 中的树结构示例和“遍历”树的递归函数。
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.
理解递归的一个好方法是在运行时逐步执行代码。
回答by Samuel
Simply put: A recursive function is a function that calls itself.
简单地说：递归函数是调用自身的函数。
回答by Imran Naqvi
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.'--');
}
}
回答by Shane Castle
Recursion is a fancy way of saying "Do this thing again until its done".
递归是一种说“再做这件事，直到它完成”的奇特方式。
Two important things to have:
有两件重要的事情：
- A base case - You've got a goal to get to.
- 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.
想象一个简单的任务：按字母顺序对一堆书进行排序。一个简单的过程是取前两本书，对它们进行排序。现在，递归部分来了：还有更多的书吗？如果是这样，再做一次。“再做一次”是递归。“还有书吗”是测试。“不，不再有书”是基本情况。
回答by Ales
Best explanation I have found when I was learning that myself is here:http://www.elated.com/articles/php-recursive-functions/
我在得知自己在这里时找到的最佳解释：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.
所以递归函数不是调用自身，而是调用另一个实例——所以它不是内存中的一个函数在做一些魔术。它在内存中的几个实例正在返回一些值——当例如函数 a 调用函数 b 时，这种行为是相同的。您有两个实例以及 if 递归函数称为自身的新实例。
Try draw memory with instances on paper - it will make sense.
尝试在纸上用实例绘制内存 - 这将是有意义的。
回答by Joel
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.
在某些时候，开发人员需要将对象解析为来自 API 或某种类型的对象或数组的响应。
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 $prefixparameter 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.
我添加了$prefix参数以使用父元素来帮助描述结束变量，以便我们可以看到该值与什么有关。它不包括空值之类的东西，但是可以从这个例子中修改。
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) } }
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"]=>
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 switchstatements 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.
我做了嵌套的 switch语句以避免与 混淆if . . . ifelse . . . else，但它几乎一样长。如果有帮助，只需询问 if 条件，我可以将它们粘贴给需要它的人。
回答by Joel
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
您也可以尝试使用谷歌搜索。请注意“您是不是要说”（单击它...）。http://www.google.com/search?q=recursion&spell=1
