通俗地说就是使用 PHP 的递归函数

Question

谁能用外行语言并使用示例向我解释 PHP 中的递归函数（不使用斐波那契）？我正在看一个例子，但斐波那契完全迷失了我！

先感谢您 ;-） 另外，您在 Web 开发中多久使用它们一次？

Answer 1

外行术语：

递归函数是一个调用自身的函数。

更深入一点：

如果函数不断调用自身，它如何知道何时停止？您设置一个条件，称为基本情况。基本情况告诉我们的递归调用何时停止，否则它将无限循环。

因为我有很强的数学背景，所以对我来说一个很好的学习例子是阶乘。从下面的评论来看，阶乘函数似乎有点太多了，我将其留在这里以防万一您需要它。

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

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

虽然我无法与目录示例竞争，但我希望这会有所帮助。

(4/20/10) 更新：

检查这个问题也很有帮助，其中接受的答案以外行术语演示了递归函数如何工作。尽管OP的问题涉及Java，但概念是相同的，

• 理解基本递归

Answer 2

一个例子是打印给定目录的任何子目录中的每个文件（如果这些目录中没有符号链接，这可能会以某种方式破坏函数）。打印所有文件的伪代码如下所示：

function printAllFiles($dir) {
    foreach (getAllDirectories($dir) as $f) {
        printAllFiles($f); // here is the recursive call
    }
    foreach (getAllFiles($dir) as $f) {
        echo $f;
    }
}

想法是先打印所有子目录，然后打印当前目录的文件。这个想法适用于所有子目录，这就是为所有子目录递归调用此函数的原因。

如果你想尝试这个例子，你必须检查特殊目录 . 和 ..，否则你会陷入调用 printAllFiles(".")< /code> 一直。此外，您必须检查要打印的内容以及当前的工作目录是什么（请参阅opendir()、getcwd()...）。

Answer 3

递归是一种不断重复的东西。就像一个从自身内部调用自身的函数。让我用一个有点伪的例子来演示：

想象一下，你和你的朋友出去喝啤酒，但如果你在午夜之前不回家，你的妻子就会让你生气。为此，我们创建 orderAndDrinkBeer($time) 函数，其中 $time 是午夜减去您喝完当前饮料并回家所需的时间。

因此，到达酒吧后，您点了第一杯啤酒并开始喝酒：

$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 :(
    }
}

现在我们只希望您没有喝足够的啤酒而喝得酩酊大醉，以至于您的妻子会让您睡在沙发上，而不管您是否在家准时 -.-

但是，是的，递归就是这样进行的。

Answer 4

它是一个调用自身的函数。它对于遍历某些重复的数据结构（例如树）很有用。 HTML DOM 是一个典型的例子。

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

为了遍历树，我们重复调用相同的函数，将当前节点的子节点传递给相同的函数。然后我们再次调用该函数，首先调用左侧节点，然后调用右侧节点。

在这个例子中，我们将获得树的最大深度。

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

最后我们调用函数

alert('Tree depth:' + walkTree(tree, 0));

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

Answer 5

简单来说：递归函数就是调用自身的函数。

Answer 6

这非常简单，当一个函数调用自身来完成未定义且有限时间的任务时。我自己的代码中的一个示例，用于填充多级类别树的函数

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

递归是“再次做这件事直到完成”的一种奇特方式。

有两件重要的事情需要具备：

1. 基本情况 - 您有一个要实现的目标。
2. 测试 - 如何知道您是否到达目的地。

想象一个简单的任务：按字母顺序对一堆书进行排序。一个简单的过程就是对前两本书进行排序。现在，递归部分来了：还有更多的书吗？如果是这样，请再做一次。 “再做一次”就是递归。 “还有更多的书吗”是测试。 “不，不再有书了”是基本情况。

Answer 8

递归是循环的替代方案，它们很少会给您的代码带来更多的清晰性和优雅性。 Progman 的回答给出了一个很好的例子，如果他不使用递归，他将被迫跟踪他当前所在的目录（这称为状态），递归允许他使用堆栈（变量所在的区域）进行簿记并存储方法的返回地址）

标准示例阶乘和斐波那契对于理解概念没有用，因为它们很容易被循环替换。

Answer 9

当我学习自己在这里时，我找到了最好的解释：http://www .elated.com/articles/php-recursive-functions/

这是因为一件事：

调用函数时在内存中创建（创建新实例）

所以递归函数不是调用它自己，而是调用其他实例 - 所以它不是内存中的一个函数在做一些魔法。它在内存中的几个实例返回自己的一些值 - 例如，当函数 a 调用函数 b 时，这种行为是相同的。您有两个实例，以及递归函数调用其自身的新实例。

试着用纸上的实例来描绘记忆——这会很有意义。

Answer 10

遍历目录树就是一个很好的例子。您可以执行类似的操作来处理数组。这是一个非常简单的递归函数，它简单地处理一个字符串、一个简单的字符串数组或任何深度的嵌套字符串数组，将字符串中的“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
}

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

Answer 11

如果您在 Anthony Forloney 的示例中添加某个值（例如“1”），一切都会很清楚：

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

原始：

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

Answer 12

基本上就是这个。它不断调用自己直到完成

void print_folder(string root)
{
    Console.WriteLine(root);
    foreach(var folder in Directory.GetDirectories(root))
    {
        print_folder(folder);
    }
}

也适用于循环！

void pretend_loop(int c)
{
    if(c==0) return;
    print "hi";
    pretend_loop(c-);
}

您也可以尝试用谷歌搜索它。请注意“您的意思是”（单击它...）。 http://www.google.com/search?q=recursion&spell= 1

Answer 13

这是阶乘与递归的一个非常简单的示例：

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

function factorial($number) { 

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

希望这对您有用。 :)

Answer 14

它是一个简单的递归示例（Y）

<前><代码>

Answer 15

这是一个实际的例子（已经有几个很好的例子了）。我只是想添加一个对几乎所有开发人员都有用的功能。

在某些时候，开发人员需要像 API 或某种类型的对象或数组的响应一样解析对象。

最初调用此函数是为了解析一个可能只包含参数的对象，但如果该对象还包含其他对象或数组怎么办？这需要解决，并且在大多数情况下，基本函数已经做到了这一点，因此该函数只需再次调用自身（在确认键或值是对象或数组之后）并解析这个新对象或数组。最终返回的是一个字符串，它在一行上单独创建每个参数以提高可读性，但您可以轻松地将值记录到日志文件或插入数据库或其他任何内容。

我添加了 $prefix 参数来使用父元素来帮助描述结束变量，以便我们可以看到该值属于什么内容。它不包括空值之类的内容，但可以从此示例中进行修改。

如果你有对象：

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

并使用：

var_dump($apiReturn);

它将返回：

对象(stdClass)#1 (4) { ["shippingInfo"]=>对象(stdClass)#2 (6) { ["fName"]=> string(4) "比尔" ["lName"]=> string(4) "测试" ["地址1"]=> string(18) “22 S. Delware St.” [“城市”]=> string(8) "钱德勒" ["state"]=>字符串（2）“AZ”[“zip”]=> int(85225) } ["电话"]=>字符串(12) "602-312-4455" ["交易详情"]=>数组(4) { ["totalAmt"]=>;字符串（6）“100.00”[“货币”]=> string(3) "美元" ["税"]=> string(4) "5.00" ["运费"]=> string(4) "5.00" } ["item"]=>;对象(stdClass)#3 (3) { ["name"]=> string(7) "T 恤" ["颜色"]=>字符串（4）“蓝色”[“itemQty”]=> int(1) } }

下面是将其解析为每个参数都带有换行符的字符串的代码：

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

这将返回对象，如下所示：

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

我执行了嵌套 switch 语句以避免与<代码>如果。 。 。否则的话。 。 。 else，但几乎一样长。如果有帮助，只需询问 if 条件，我可以将它们粘贴给需要的人。

Answer 16

用于 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;

}

该函数不断使用计算结果调用自身，直到达到 Kaprekar 常数，此时它将返回计算的次数。

/edit 对于任何不知道 Kaprekars Constant 的人，它需要输入 4 位数字，其中至少有两个不同的数字。

Answer 17

当某些内容包含或使用相似版本时，就会发生递归
当具体谈论计算机编程时，
当函数调用自身时，就会发生递归。

以下链接帮助我更好地理解递归，即使我认为这是迄今为止我学到的最好的链接。

它附带了一个示例来了解内部（递归）函数在执行时如何调用。

请仔细阅读这篇文章，我已经粘贴了测试程序，以防文章被扔掉。您可以在本地服务器上运行该程序以查看其运行情况。

https://www.elated.com/php-recursive-functions/

<?php

function factorial( $n ) {

  // Base case
  if ( $n == 0 ) {
    echo "Base case: $n = 0. Returning 1...<br>";
    return 1;
  }

  // Recursion
  echo "$n = $n: Computing $n * factorial( " . ($n-1) . " )...<br>";
  $result = ( $n * factorial( $n-1 ) );
  echo "Result of $n * factorial( " . ($n-1) . " ) = $result. Returning $result...<br>";
  return $result;
}

echo "The factorial of 5 is: " . factorial( 5 );

?>