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!

谁能给我解释一下PHP中的递归函数(不使用斐波那契)吗?我在看一个例子，但是斐波那契完全把我弄丢了!

Thank you in advance ;-) Also how often do you use them in web development?

预先谢谢你;-)还有你多久使用他们在网络开发?

16 个解决方案

#1

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.

关于在web开发中使用递归函数，我个人不使用递归调用。我并不认为依赖递归是不好的做法，但是它们不应该是您的首选。如果使用不当，它们可能是致命的。

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,

检查这个问题也是很有帮助的，在这个问题中，被接受的答案用外行术语表示了递归函数是如何工作的。尽管OP的问题涉及Java，但概念是一样的，

• Understanding basic recursion
• 了解基本的递归

#2

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()、…)。

#3

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.

但这就是递归。

#4

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.

理解递归的一个好方法是在运行时逐步执行代码。

#5

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

简单地说:递归函数是一个调用自身的函数。

#6

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. 基本情况——你有一个目标。
3. A test - How to know if you've got to where you're going.
4. 一个测试——如何知道你要去哪里。

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.

想象一个简单的任务:按字母顺序排列一堆书。一个简单的过程是把前两本书分类。现在，递归部分来了:还有书吗?如果是的话，再做一次。“再做一次”就是递归。“还有书吗”是测试。“不，不再有书”是基本情况。

#7

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

当一个函数调用自己来完成一个没有定义和有限时间的任务时，它是非常简单的。我自己的代码中的一个例子，用于用多级类别树填充a

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

#8

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时的行为相同。

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

试着在纸上用实例来画出记忆——这是有意义的。

#9

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)

递归是循环的一种替代方法，它很少会给代码带来更多的清晰和优雅。一个很好的例子是由Progman的回答,如果他不会使用递归他将*跟踪目录他目前(这称为状态)递归允许他做记账使用堆栈(区域变量和返回地址的方法存储)

The standard examples factorial and Fibonacci are not useful for understanding the concept because they're easy to replace by a loop.

标准示例factorial和Fibonacci对于理解这个概念没有用处，因为它们很容易被循环替换。

#10

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

#11

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.

这个函数最初被调用来解析一个可能包含参数的对象，但是如果对象还包含其他对象或数组呢?这将需要处理，而且在大多数情况下，基本函数已经这样做了，所以这个函数会再次调用它自己(在确认键或值是一个对象或一个数组之后)并解析这个新的对象或数组。最终返回的是一个字符串，它自己在一行上创建每个参数，以提高可读性，但是您也可以很容易地将这些值记录到日志文件中，或者插入到DB或其他文件中。

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.

我添加了$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) } }

对象(stdClass)#1 (4) {[shippingInfo]=>对象(stdClass)#2 (6) {[fName]=>字符串(4)“比尔”(“lName”)= >字符串(4)“测试”(“address1”)= >字符串(18)“22美国特拉华州圣”["城市"]= >字符串(8)“钱德勒”(“状态”)= >字符串(2)“阿兹”[" zip "]= > int(85225)}(“电话”)= >字符串(12)"602-312-4455" ["transactionDetails"]=>数组(4){["totalAmt"]=>字符串(6)“100.00”(“货币”)= >字符串(3)“美元”(“税”)= >字符串(4)“5.00”(“货运”)= >字符串(4)“5.00”}(“项目”)= >对象(stdClass)# 3(3){(“名字”)= >字符串(7)“t恤”(“颜色”)= >字符串(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.

我做了嵌套的switch语句，以避免与if混淆。ifelse。还有，但是差不多一样长。如果它有帮助，只要询问条件，我就可以把它们粘贴到需要的人那里。

#12

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:

遍历目录树就是一个很好的例子。您可以做一些类似于处理数组的事情。这是一个非常简单的递归函数，它只处理一个字符串、一个简单的字符串数组或一个嵌套的任意深度的字符串数组，将字符串中的“hello”实例替换为“goodbye”或数组或任何子数组的值:

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.

它知道何时退出，因为在某些时候，它正在处理的“事物”不是一个数组。例如，如果您调用replaceHello(“hello”)，它将返回“goodbye”。如果您向它发送一个字符串数组，尽管它将为数组的每个成员调用一次自己，然后返回经过处理的数组。

#13

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

如果你在Anthony Forloney的例子中加入一个特定的值(比如“1”)，一切都会变得清晰:

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

#14

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.

阶乘是一个非常简单的数学概念。它们写得像5!这意味着5 * 4 * 3 * 2 * 1。所以6 !是720和4 !是24。

function factorial($number) { 

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

hope this is usefull for you. :)

希望这对你有用。:)

#15

It work a simple example recursive (Y)

这是一个简单的递归例子(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);

 ?>

#16

Recursion used for Kaprekar's constant

用于Kaprekar常数的递归

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.

函数一直调用自己的计算结果，直到它到达Kaprekars常量，它将返回计算的次数。

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

/编辑对于任何不知道Kaprekars常量的人来说，它需要输入至少两个不同数字的4位数字。