使用递归可以解决哪些问题？

Question

今天我做了一个方法，在php中使用递归并且对它感兴趣。实际上递归可以解决什么问题？为什么我们可以使用递归？

我开始在网上搜索并搜索和搜索，但找不到任何东西。

所以我问，我们可以做什么用递归？

是否有一些限制？我们不能用递归做但我们可以使用标准循环？我想知道我是否可以经常在代码中正常使用递归。

Answer 1

每种迭代通过任何数据结构的类型都可以用递归完成。事实上，你可以替换的每一个循环构造像for，while，do while，foreach等简单递归：

function factorial($n) { 
    $result = $n < 0 ? -1 : 1; 
    for($i = abs($n), $i > 1; $i--) { 
    $result *= $i; 
    } 
    return $result; 
} 

可以写成：

function factorial($n) { 
    $forHelper = function($result, $i) { 
    return $i === 1 ? $result : $forHelper($result * $i, $i - 1); 
    } 
    return $forHelper($n < 0 ? -1 : 1, abs($n)); 
} 

这被称为尾递归。在某些语言中，上述两者产生非常相似的运行时代码，但不是PHP。它为每个呼叫使用一些内存。对我来说，两者都具有相同的可读性，但我敢打赌，大多数程序员会发现使用循环更容易，尤其是在嵌套时。

function treeDepth($node) { 
    if($node === null) { 
    return 0; 
    } else { 
    return 1 + max(treeDepth($node->left), treeDepth($node->right)); 
    } 
} 

这里的迭代解决方案需要跟踪它需要去的地方的一些方式：

，你遍历一个图或树中的一些算法将使用递归而非迭代有一个简单的版本因此您正在做一些由递归版本自动处理的内务管理。

function treeDepth($node) { 
    $max = 0; 
    $backtrack = [[0, $node]]; 
    while(count($backtrack)) { 
    list($depth, $node) = array_pop($backtrack); 
    while($node !== null) { 
     array_push($backtrack, [++$depth, $node->right]); 
     $node = $node->left; 
    } 
    $max = max($max, $depth); 
    } 
    return $max; 
} 

该限制取决于语言。在PHP中，它为每个未分配给简单循环的调用帧分配一些内存。节点遍历总是使用内存，因为该过程本身是递归的。

最终，您应该按照让代码尽可能清晰而不考虑优化的方式进行编码。在最清晰的位置使用循环构造，并在最清晰的位置使用递归。只有当您发现性能问题时，您才应该对最常用的部分进行配置和重写。我用它来保留原始代码作为注释，如果它很短并记录更复杂的迭代版本中实际发生的事情。在PHP函数调用本身是昂贵的。

Answer 2

我们可以使用递归做什么？

解决递归问题。亲子问题，每个孩子都可以再次成为父母，这是最常见的问题。

function doSomethingWithNode($node) 
{ 
    // Do something with $node 

    // Loop over all childs, and run this code for those childs too, and for those childs, and for those childs, and ... 
    foreach($node->getChilds() as $child) { 
     doSomethingWithNode($child); 
    } 
} 

doSomethingWithNode($rootNode); 

是否有一定的局限性？

是的。 PHP（以及其他编程语言）会跟踪哪些代码调用哪个函数，因此它知道函数返回后继续哪里。这被称为call stack。将新条目添加到call stack将需要一些内存和一些时间。当你有很多（百万）迭代时，第一个CAN主要会导致问题。

根据您的安装，call stack甚至可能会受到限制。默认情况下不是。通过安装xdebug -extension，它最多可以为您提供100个嵌套调用（默认情况下，可以在配置中进行更改）。在这些设置中，它将导致致命错误（example）。

事情我们不能用递归做但是用标准循环我们可以吗？我不知道现在是否可以在我的代码中正常使用递归

由于上述限制，应谨慎使用递归。当你可以使用普通循环或for循环解决它时：使用正常循环。大多数情况下，它会导致更容易阅读代码。

当您关心可移植性时（例如编写开源项目时），您可能想要考虑xdebug用户。