用通俗易懂的语言解释，什么是使用PHP实现的递归函数？

Question

请问有没有人能用通俗易懂的语言和例子来解释PHP中的递归函数（不使用斐波那契数列）？我看了一个例子，但是斐波那契数列完全让我迷糊了！

谢谢你提前的帮助 ;-) 此外，你在Web开发中使用递归函数的频率有多高？

- Imran

---

仔细阅读https://dev59.com/cXE85IYBdhLWcg3wtV1T，最终就会理解。 - Kevin

您可以尝试在Google上点击“Did You Mean”链接：http://www.google.com/search?hl=en&q=recursion，来获取更准确的搜索结果。 - Gordon

@kevin，也许你应该将评论写成“重复问题 https://dev59.com/cXE85IYBdhLWcg3wtV1T” ;) - Progman

@Kevin：但你忘记了基本情况！他不会通过那种方式学习递归，他只会一直点击它，直到堆栈溢出。 :( - C. A. McCann

考虑到我们所在的网站，我认为这是合适的。 - Amber

Answer 1

通俗易懂：

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

更深入的解释：

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

对我来说，一个很好的学习例子是factorial。根据下面的评论，阶乘函数可能有些复杂，但我还是会在这里留下它，以防您需要它。

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，但概念是相同的。

• 理解基本递归

- Anthony Forloney

---

虽然你的例子解释得很好，但这个例子在普通人的术语中几乎不能被视为一个例子。如果 OP 在理解基于斐波那契数列的递归时有点困难，我想阶乘也不行。特别是涉及这些数学定义时。 - Decent Dabbler

@fireeyedboy，stereofrog：在大学里，我学递归时也学了阶乘函数，这让我恍然大悟。虽然OP和我可能有不同的数学背景，但为了简洁起见，我省略了阶乘的定义，并强调了我对递归的通俗解释。 - Anthony Forloney

函数没有结束条件（基本情况）的要求，这使得您的定义略有不准确。（尽管在PHP中必须这样做，否则您最终会遇到堆栈溢出） - Yacoby

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(".")中卡住。此外，你必须检查要打印什么以及你当前的工作目录是什么（参见opendir()、getcwd()等函数）。

- Progman

---

我更喜欢这个答案，因为它是实际应用的东西，而不是阶乘那个。有多少人必须要计算阶乘，为什么要递归地计算阶乘呢（也许可以使用记忆化，但此时，为什么不从一开始就使用查找表呢）。 - davidtbernal

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

现在就希望你没有喝太多啤酒，导致醉醺醺的回家后，妻子不管你有没有准时回家都让你睡沙发上。

但是，这基本上就是递归的工作原理。

- Freyr

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

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

- James Westgate

Answer 5

简而言之，递归函数是调用自身的函数。

- Samuel

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

- Imran Naqvi

Answer 7

递归是一种说法，它的意思是“重复执行某个任务直到完成”。

有两个重要的要素：

1. 基本情况 - 你有一个要达到的目标。
2. 测试 - 如何知道是否已经达到了目标。

想象一个简单的任务：按字母顺序对一堆书进行排序。一个简单的过程是取出前两本书并将它们排序。现在，这里涉及到递归: 是否还有更多的书？如果是这样，再次执行。 "再次执行" 就是递归。 "还有更多的书吗" 就是测试。而 "不，没有更多的书了" 就是基本情况。

- Shane Castle

Answer 8

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

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

- stacker

Answer 9

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

原因只有一个：

当函数被调用时，它会在内存中创建一个新实例（新的实例被创建）。

所以递归函数并没有调用自身，而是调用其他实例 - 所以它不是一个函数在内存中执行某些魔法。它是在内存中有几个实例，它们返回一些值给自己 - 当函数a调用函数b时，行为也是相同的。你也会有两个实例，就像递归函数调用自己的新实例一样。

试着在纸上画出实例的内存图 - 这会让你明白。

- Ales

Answer 10

使用递归计算卡普雷卡常数

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常数为止，然后它将返回计算次数。/编辑 对于那些不了解Kaprekar常数的人，它需要一个由至少两个不同数字组成的4位数字输入。

- Bart