使用递归函数有什么好处？

wayde算法

我最近发现了著名的（或不那么著名的）递归函数，并发现这个概念非常有趣。然而，在我阅读的过程中，我对这种用法有一些疑问。

1st 使用递归函数的优点是什么？因为我无法理解这样做的好处：

<?php
function recursiveFunction($num)
{
    if ($num != 0) {
        echo "O valor é $num. <br>";
        recursiveFunction(--$num);
    }
}
recursiveFunction(10);

对这个：

<?php
function recursiveFunction($num)
{
    for ($i = $num; $i != 0; $i--) {
        echo "O valor é $i <br>";
    }
}
recursiveFunction(10);

2、内存消耗如何？因为据我所知，递归函数是在另一个函数中执行的（然后进行循环重复）。根据计算的大小，使用递归函数会影响我的应用程序的性能吗？

第三我应该使用递归函数而不是常规循环重复（例如for/while）吗？使用递归函数的理想情况是什么？

4 个优秀答案

最佳回答

真的递归被高估了。

我意识到递归函数教学通常不正确（当然在我看来），当总是使用的示例是做一些顺序而不是递归的事情时。当然，它可以是递归的，但是当您使用相同的标准分解后续运行时，递归就可以了。我什至明白递归模拟序列是最简单的教学方法，但它会让人觉得这是递归的最佳方式。

消耗

如果语言不提供优化，内存和处理消耗可能比循环版本高得多。它可能会导致运行时问题，例如堆栈溢出。当前的 PHP（截至本回复日期）未优化。

在两个分析的向量中，函数调用的开销很大。不考虑算法本身，每次调用都有一个成本，主要是准备函数的环境并返回到原始状态。并且为了确保它可以恢复到原始状态，应用程序的堆栈资源正在被消耗。

注意优化语言将递归转化为迭代。移植迭代对计算机更好。在某些情况下，递归可能更适合人类理解。

这种优化只是为了消除上面提到的调用和成本，而不是改变算法的执行方式。

需要注意的是，这并不影响算法的复杂度。两者都是线性的、对数的、指数的或其他的，取决于算法的具体需要，与递归或迭代无关。

可以进行手动优化，例如记忆。在迭代中它是一种帮助，在递归中它可以是强制性的，但仍然不能解决所有问题。这是一种防止递归发生或降低其深度的方法，这可能是它工作与否之间的区别。

哪里有趣

在运行固有递归算法时，递归函数很有趣。例如，处理数据树通常最好以递归方式表达。

问题中的示例显然更糟糕的是递归完成。这是一个简单的序列，不需要复杂的递归（有些人不同意）。

如果不明显它应该是递归的，那么它可能不应该是。递归的目的是能够按照你认为的问题做一些事情。当他推动酒吧时，他滥用语言看起来更聪明。如果机制难以理解并且没有提供明显的优势，最好不要使用它。在感觉自然时使用。如果你好好学习并意识到它的用处，你就会明白什么时候使用它。

除非该语言没有循环特性，否则只有在明确使代码对每个人都更具可读性时才应该使用递归，而不仅仅是倾向于喜欢递归的学者。主要是没有优化的语言。

更多信息

我不会详细介绍，因为几乎所有内容都已经在我已经问过的有关该主题的问题中得到了回答。尽管 utluiz 在那里的回答更直接地回答了这个问题，但我发现 mgibsonbr 的回答对于这里的上下文更有趣。 52Maniero.. 6 年，3 月 前

TL; 博士

所有递归代码都可以转换为迭代形式，但是某些算法自然是递归的，并且更容易以这种方式表示。

例如，考虑遍历树或图形的所有节点，处理目录和子目录中的所有文件，等等。

在迭代模式下，您负责使用某些数据结构（通常是堆栈）手动管理算法每个步骤的状态，而在递归模式下，您可以通过使用自动分配的变量和参数将此功能委托给您的编程语言到每个方法执行开始时的执行堆栈。

例子

要回答这些问题，请考虑一些更复杂的事情。我提取了伪代码来遍历维基百科树。

递归方法

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

迭代法

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ? null)
    if (node ? null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ? null and lastnodevisited ? peeknode.right) 
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop()

答案

1st 使用递归函数的优点是什么？

在您的示例中几乎没有优势，但是在我上面的内容中，我们清楚地看到递归方法：

  • 它更好地表达了功能。编程工作使这种能力变得如此沉重。
  • 它更紧凑。更少的代码意味着更容易的维护、更少的错误机会等等。
  • 自动状态管理。在迭代示例中使用了一个堆栈（stack）。现在想想内存管理不是自动的语言。例如，在 C 中，您必须添加代码以在每次迭代时从堆栈中分配和释放元素。

2、内存消耗如何？

这取决于角色。通常，您应该进行内存和时间复杂度分析以分析差异，但很明显，在绝大多数情况下，递归例程消耗更多内存并需要更多执行周期。

递归例程通常通过在每次递归调用时重新分配变量来使用更多内存，但例如，如果值保存在列表或堆栈中，则迭代例程可以使用相同数量的内存。

在迭代模式下，无论好坏，您都可以控制。有可能创建比递归版本更优化的例程。但这不应该作为规则，毕竟有优秀的递归实现比一般的迭代实现更有效。

此外，效率在很大程度上取决于执行次数和递归级别。与排序例程一样，某些实现在迭代次数较少时效果最佳，而其他实现在迭代次数较多时效果最佳。一些递归实现更适合小型处理。例如，在此站点上查看 Fibonacci 的性能，其中n <= 5递归版本更好。

在一个非常简单的示例中，Fibonacci 递归函数具有指数复杂性，而该版本可以使用两个或三个简单变量来实现，因此具有恒定的内存使用量。

另一方面，当处理的元素或数字的数量很大时，递归例程几乎总是最终需要以其迭代版本重写，毕竟递归在内存和数据堆栈中都有敏感限制。

最重要的是，有一些技术可以提高递归例程的性能和容量，例如：

第三我应该使用递归函数而不是常规循环重复（例如 for/while）吗？使用递归函数的理想情况是什么？

只有当该算法更好地递归表示并且该算法的一般用法不会超过递归限制时，才应该这样做。

我相信理想的情况已经在上面举例说明了，即：

  • 固有的递归算法，最好用这种格式表达
  • 计算使用量适中，以免超过递归限制

 26👍🏻

utluiz.. 6 年，3 月 前

  1. 递归函数对于问题本身是自然定义的并且递归解决方案最简单的情况是一个优势。起初这可能看起来很奇怪，因为递归看起来很复杂和令人困惑，但是随着时间和理解（也有大量练习），您将学会识别问题的最佳解决方案。
  2. 通常递归代表内存开销，这是因为函数的每次调用都会在调用堆栈中分配一个帧，因此递归函数进行的每次新调用都会在堆栈上分配一个新的帧，并且每个新的帧都会积累更多的内存，所有这些仅当所有递归调用都到达断点时才会释放内存（在您的示例中，当 $num 为 == 0 时）。如果递归函数对自身进行了太多调用（在堆栈上积累了太多“帧”），则会发生“堆栈溢出”。如果您想更好地了解调用堆栈是什么以及堆栈溢出是如何发生的，我建议您阅读这个问题和提供的答案。
  3. 答案是生活有多艰难，这要看情况。正如我之前提到的，递归的优势在于本质上是递归的并且递归解决方案是最简单和最直接的问题，一个经典的例子是二叉树的操作，一种固有的递归数据结构。我最后的建议是：学习递归，理解它是如何工作的，练习，最终你会知道使用它的最佳时机。

 12👍🏻

BrunoRB.. 6 年，3 月 前

任何没有在实践中进行实验的人最终都无法理解理论。所以展示一个在“现实世界”中使用的实际例子总是好的。

了解何时部署的基本技巧是何时需要执行多个可变数量的重复循环。

当您确定可以用 X 次重复循环解决某些问题时，只要没有太多循环，就可以应用多个循环。例如，10 个循环很多，因此考虑使用递归就是这种情况。

想象

while(){
    while(){
        while(){
            while(){
                while(){
                    while(){
                        while(){
                            while(){
                                while(){
                                    while(){

这在递归中看起来如何？

function foo()
    while(){
       foo();

下面是一个实际的使用示例。

在这种情况下，我需要创建一个函数来规范化路径（文件系统）。在 PHP 中有一个函数，realpath()但这个函数只对现有路径进行规范化。下面的函数和它一样，realpath()不同的是它忽略了路径是否存在。目的只是为了正常化。

这是一个使用递归的实际例子。在这种情况下，不适合手动使用多个循环。

$path_canonicalize = function($str, $started = false) use(&$path_canonicalize)
{
    $str = str_replace('/', DIRECTORY_SEPARATOR, $str).DIRECTORY_SEPARATOR;

    if (!$started)
        $str = preg_replace("/".preg_quote(DIRECTORY_SEPARATOR, "'".DIRECTORY_SEPARATOR."'")."{2,}/", DIRECTORY_SEPARATOR, $str);

    $pos = strpos($str, '..'.DIRECTORY_SEPARATOR);
    if ($pos !== false)
    {
        $part = trim(substr($str, 0, $pos), DIRECTORY_SEPARATOR);
        $str = $path_canonicalize(trim(substr($part, 0, strrpos($part, DIRECTORY_SEPARATOR)), DIRECTORY_SEPARATOR).DIRECTORY_SEPARATOR.trim(substr($str, $pos+3), DIRECTORY_SEPARATOR), true);
    }
    return rtrim($str, DIRECTORY_SEPARATOR);
};

/*
Try those cases to check the consistency:
$str = __DIR__.'/template//////../header//..';
$str = __DIR__.'/template///..///../header//..';
$str = __DIR__.'/template/../header/..';
$str = __DIR__.'/template/../header/../';
$str = __DIR__.'/template/../header/..//';
$str = __DIR__.'/template/../header/..///';
$str = __DIR__.'/template/../header/..///..';
$str = __DIR__.'/template/../header/..///../';
$str = __DIR__.'/template\\..\\header\\..';
*/
$str = __DIR__.'/template/../header/..///..//';
echo 'original: '.$str.PHP_EOL;
echo 'normalized: '.$path_canonicalize($str).PHP_EOL;

5👍🏻

原文地址：https://qa.1r1g.cn/pt/ask/7536021/#

扩展阅读：

Quando ocorre o Stack Overflow?（堆栈溢出何时发生？）

发表回复

京ICP备15027918号-1