有没有可以用循环完成的递归操作？

#1 楼

是的，没有。最终，没有任何递归可以计算出循环无法做到的事，但是循环需要花费更多的精力。因此，递归可以使循环做不到的一件事就是使某些任务变得非常容易。

走一棵树。递归地走树很愚蠢。这是世界上最自然的事情。用循环走一棵树要简单得多。您必须维护堆栈或其他数据结构来跟踪您所做的事情。

通常，问题的递归解决方案更漂亮。这是一个技术术语，很重要。

#2 楼

不。

深入了解必要最小值的基础知识以便进行计算，您只需要能够循环即可（仅这是不够的，而是必要的组件）。没关系。

任何可以实现Turing Machine的编程语言都称为Turing complete。还有很多语言正在完善中。

我最喜欢的语言是“实际上有效吗？”。图灵完整性是FRACTRAN的图灵完整性。它具有一个循环结构，您可以在其中实现图灵机。因此，任何可计算的内容都可以用没有递归的语言来实现。因此，就简单循环无法实现的可计算性而言，递归没有给您带来任何好处。

这实际上可以归结为以下几点：


可计算是可在图灵机上计算的。
可以实现图灵机的任何语言（称为图灵完成），可以计算任何其他语言可以实现的任何功能
，因为存在图灵机的语言缺乏递归（并且还有其他一些只有当您进入其他一些esolang中时才具有递归），这确实是对递归无法做的事，而您不能对循环做任何事（对循环也无能为力）

这并不是说有些问题类更容易通过递归而不是循环来考虑，而通过循环而不是递归来考虑。但是，这些工具同样功能强大。

虽然我将其带到了“ esolang”极端（主要是因为您可以找到图灵完整且以相当奇怪的方式实现的事物），但这并不意味着esolangs绝对不是可选的。图灵有一个不完整的完整清单，包括聚会魔术师，Sendmail，MediaWiki模板和Scala类型系统。在实际执行任何实际操作时，这些方法中的许多方法都不是最佳方法，只是您可以使用这些工具计算任何可计算的内容。进入一种称为尾调用的特殊类型的递归。

如果有的话，可以说一个阶乘方法写为：

 int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}
 

这种类型的递归将被重写为循环-不使用堆栈。与编写等效循环相比，此类方法的确确实通常更优雅，更易于理解，但是同样，对于每个递归调用都可以编写等效循环，并且对于每个循环都可以编写递归调用。

有时候，将简单循环转换为尾部调用和递归调用也很费劲，而且更难理解。


如果您想了解它的理论方面，参见图灵教堂的论文。您也可能会发现CS.SE上的教堂折磨论题很有用。

#3 楼

在任何情况下，只能使用递归而不是循环来完成任务吗？


您总是可以将递归算法转换为循环，从而使用后进先出数据结构（AKA堆栈）存储临时状态，因为递归调用正是这样，将当前状态存储在堆栈中，继续进行算法，然后再恢复该状态。如此简短的回答是：不，没有这样的情况。

但是，可以为“是”进行论证。让我们举一个具体的简单示例：合并排序。您需要将数据分为两部分，对部分进行合并排序，然后将它们组合在一起。即使您没有进行实际的编程语言函数调用来进行合并排序以对部件进行合并排序，您也需要实现与实际执行函数调用相同的功能（将状态推入自己的堆栈，跳转至使用不同的起始参数开始循环，然后从堆栈中弹出状态）。

是递归，如果您自己实现递归调用，则作为单独的“推送状态”和“跳转到开始”和“流行状态”步骤？答案是：不，它仍不称为递归，它称为具有显式堆栈的迭代（如果要使用已建立的术语）。


请注意，这也取决于“任务”的定义。如果任务是排序的，那么您可以使用许多算法来实现，其中许多不需要任何递归。如果任务是实现特定的算法（如merge sort），则适用上述歧义。

因此，让我们考虑一下问题，是否存在通用任务，对于这些任务，仅存在类似于递归的算法。根据问题下@WizardOfMenlo的评论，Ackermann函数就是一个简单的例子。因此，即使可以使用不同的计算机程序构造（使用显式堆栈进行迭代）来实现，递归的概念也是独立存在的。

#4 楼

这取决于您对“递归”的定义。

如果我们严格要求它涉及调用堆栈（或使用任何用于维护程序状态的机制），那么我们总是可以用某种东西来代替它。那不是。确实，自然导致大量使用递归的语言倾向于使编译器大量使用尾调用优化，因此您编写的是递归的，但是运行的是迭代的。

但是让我们考虑一下

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}
 

进行第一个递归调用迭代很容易：

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}
 

然后我们可以清理掉goto，以避开速激肽和Dijkstra的阴影：

 public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}
 

但是要删除其他递归调用，我们将必须将某些调用的值存储到堆栈中：

 
考虑到此方法已被编译为什么，我们已将使用调用堆栈的代码实现了递归，将代码递归为未实现的代码（这样做的话，已转换的代码将引发堆栈溢出异常，即使代码中的值很小，也只需要花费非常长的时间即可返回[请参阅如何防止我的Ackerman函数溢出堆栈？进行进一步优化，使其实际上返回更多可能的输入]）。
 
考虑到一般如何实现递归，我们已经将使用调用堆栈的代码转换为使用不同堆栈来保存挂起操作的代码。因此，我们可以认为，在较低的级别上考虑它仍然是递归的。
 
在该级别上，确实没有其他方法可以解决。因此，如果您确实认为该方法是递归的，那么确实有些事情如果没有它我们是无法做的。通常，尽管我们不标记此类代码递归。递归一词非常有用，因为它涵盖了某些方法集，并为我们提供了一种讨论它们的方法，而我们不再使用其中一种方法。
 
当然，所有这些都假定您已经一个选择。既有禁止递归调用的语言，又有缺乏迭代必要的循环结构的语言。

评论
如果调用堆栈是有界的，或者可以访问调用堆栈之外的无界内存，则只能用等效的东西替换调用堆栈。下推式自动机可以解决一大类问题，这些问题具有无限的调用堆栈，但否则只能具有有限数量的状态。



 –超级猫

 15年11月24日，0：10 
这是最好的答案，也许是唯一的正确答案。甚至第二个示例仍然是递归的，在这个级别上，原始问题的答案是否定的。有了更广泛的递归定义，就无法避免Ackermann函数的递归。



 – Gerrit

 15年11月24日在10:26 
@gerrit并缩小了范围，但确实避免了。最终，它归结为我们所做的或未应用我们用于某些代码的有用标签的边缘。



 –琼·汉娜（Jon Hanna）

 15年11月24日在10:34 
加入该网站以对此进行投票。 Ackermann函数本质上是/ is /递归的。用循环和堆栈实现递归结构并不能使其成为迭代解决方案，您只是将递归移到了用户空间中。



 –亚伦·麦克米林（Aaron McMillin）

 2015年11月25日在16:22 

#5 楼

经典的答案是“否”，但请允许我详细说明为什么我认为“是”是更好的答案。

在继续之前，让我们先走开一点：从可计算性和复杂性立场：

如果允许在循环时使用辅助堆栈，则答案为“否”。
如果不允许在循环时使用任何额外的数据，答案为“是”。 br />
好吧，现在让我们将一只脚放在实践领域，将另一只脚放在理论领域。

调用堆栈是控制结构，而手动堆栈是
控制和数据不是相同的概念，但是从可计算性或复杂性的角度来看，它们可以彼此简化（或彼此“模拟”），从某种意义上说，它们是等效的。 />什么时候这个区别很重要？使用实际工具时。举个例子：
假设您正在实施N路mergesort。您可能有一个遍及每个for段的N循环，分别对它们调用mergesort，然后合并结果。
如何将其与OpenMP并行化？
在递归领域中，这非常简单：
只需将#pragma omp parallel for放在从1到N的循环中就可以了。
在迭代领域中，您不能这样做。您必须手动生成线程并手动将它们传递给适当的数据，以便它们知道该怎么做。
另一方面，还有其他工具（例如自动矢量化程序，例如#pragma vector）可以与循环一起使用，但是完全可以递归是没有用的。
要点在于，仅仅因为您可以证明两个范式在数学上是等价的，但这并不意味着它们在实践中是相等的。
在一个范式中实现自动化可能并不容易（例如，循环并行化）可能很难在另一种范式中解决。
即：一种范式的工具不会自动转换为其他范式。

因此，如果您需要一种工具来解决问题，则该工具很可能仅适用于一种特定的方法，因此即使您可以数学证明问题可以解决，您也将无法使用其他方法来解决问题。无论哪种方式都可以解决。

#6 楼

撇开理论推理，让我们从（硬件或虚拟）机器的角度看一下递归和循环是什么样的。递归是控制流的组合，它允许开始执行某些代码并在完成时返回（在忽略信号和异常的情况下，在简化视图中）与传递给该其他代码（自变量）并从中返回的数据它（结果）。通常不涉及显式的内存管理，但是会隐式分配堆栈内存以保存返回地址，参数，结果和中间本地数据。

循环是控制流和本地数据的组合。将其与递归进行比较，我们可以看到这种情况下的数据量是固定的。打破此限制的唯一方法是使用可以在需要时分配（和释放）的动态内存（也称为堆）。

总结：


递归案例=控制流+堆栈（+堆）
循环案例=控制流+堆

假设控制流部分功能强大，唯一的区别在于可用的内存类型。因此，我们剩下4种情况（表达能力在括号中列出）：


没有堆栈，没有堆：递归和动态结构是不可能的。 （递归=循环）
堆栈，没有堆：递归可以，动态结构是不可能的。 （递归>循环）
没有堆栈，堆：不可能递归，动态结构也可以。 （递归=循环）
堆栈，堆：递归和动态结构都可以。 （递归=循环）

如果游戏规则更严格，并且不允许递归实现使用循环，则改为使用：


没有堆栈，没有堆：递归和动态结构是不可能的。 （递归<循环）
堆栈，没有堆：递归可以，动态结构是不可能的。 （递归>循环）
没有堆栈，堆：不可能进行递归，可以使用动态结构。 （递归<循环）
堆栈，堆：递归和动态结构都可以。 （递归=循环）

与以前的方案的主要区别在于，缺少堆栈内存将导致递归，而没有循环则在执行过程中没有循环执行比代码行更多的步骤。

#7 楼

是。使用递归可以轻松完成一些常见任务，而使用循环则很容易完成：


导致堆栈溢出。
使初学者程序员完全困惑。
创建快速外观实际上是O（n ^ n）的函数。

#8 楼

递归函数和原始递归函数之间有区别。原始递归函数是使用循环计算的，其中每个循环的最大迭代计数是在循环执行开始之前计算的。 （这里的“递归”与使用递归无关）。

严格的递归函数的功能远不如递归函数。如果您使用了使用递归的函数，您将得到相同的结果，其中必须事先计算最大递归深度。

#9 楼

如果您使用c ++进行编程，并使用c ++ 11，则必须使用递归完成一件事：constexpr函数。但是该标准将其限制为512，如本答案所述。在这种情况下无法使用循环，因为在这种情况下该函数不能为constexpr，但是在c ++ 14中已对此进行了更改。

#10 楼

如果递归调用是递归函数的第一个或最后一个语句（不包括条件检查），则很容易将其转换为循环结构。
但是如果该函数之前执行了其他操作并且在进行递归调用之后，将其转换为循环会很麻烦。
如果函数具有多个递归调用，则将其转换为仅使用循环的代码几乎是不可能的。需要一些堆栈来跟上数据。在递归中，调用堆栈本身将作为数据堆栈。

#11 楼

我同意其他问题。递归与循环无关。

但是，在我看来，递归非常危险。首先，对于某些更难理解的代码实际发生了什么。其次，至少对于C ++（我不确定Java），每个递归步骤都会对内存产生影响，因为每个方法调用都会导致内存累积和方法标头的初始化。这样，您可以炸毁堆栈。只需尝试递归输入值较高的斐波那契数。