递归函数的最小空间复杂度是否为O(N)？

Question

我在思考递归函数。以一个简单的函数为例，比如递归打印链表：

void print(list *list){
  if(list){
     cout << list->data
     print(list->next);
  }
}

起初，这个函数似乎相当无害，但是它不是在每个堆栈帧中存储一个地址（由变量列表标记）吗？假设没有尾调用优化。我们需要N个地址的空间，其中N是列表的大小。所需的空间与列表的大小成比例线性增长。

我想不出如何在没有至少一个本地变量或参数存储在堆栈上的情况下实现递归函数。因此，似乎每个递归函数最多都具有线性空间复杂度。如果是这种情况，那么使用迭代而不是递归几乎总是明智的选择。

- ordinary

---

编译器可以轻松地进行优化，以便不在堆栈上保留任何内容。 - David Schwartz

@DavidSchwartz：当然，但是OP在中间段落中声明，“假设没有尾调用优化”。 - Gabe

Answer 1

虽然所有的非优化函数调用都会占用一个栈帧，但并不总是递归算法对N个元素进行操作就需要大小为O(N)的堆栈。

例如，递归的树遍历算法和递归的快速排序算法都使用O(lg N)的堆栈帧。

- Gabe

---

这是一个非常好的观点。我应该说是一个非常量级的空间，但问题的本质仍然是相同的。 - ordinary

Answer 2

你说得对，这段代码的空间复杂度仅与列表大小成线性关系，假设没有尾调用优化。

一般来说，递归会让事情变得更慢且占用更多内存。但并非总是可以通过迭代实现进行渐进式改进，因为对于非尾递归函数，您仍需要在迭代实现中手动维护堆栈，因此您仍将使用相同数量的内存。

想象一下深度优先遍历。您需要将每个节点和需要访问的下一个子节点一起存储在堆栈上，以便在从访问其子节点后返回之后，您知道要到达哪个节点。递归使这变得非常容易，因为它抽象了所有丑陋的记账工作。迭代实现不会在渐近意义下更好，我也期望实际差异很小。

很多时候，递归使事情更容易而不会牺牲任何东西。在您的情况下，没有必要使用它 - 这只是递归的教学示例。

- IVlad

---

哈哈！我一直在评论框中输入问题，但在我提交之前，你就进行了编辑并回答了确切的问题。太有趣了。但我还有一个问题。你提到递归会带来速度上的牺牲。为什么会这样？ - ordinary

@ordinary - 抱歉，我通常需要大约5分钟才能把所有东西都说出来:P。由于调用函数需要时间，因此会有速度上的牺牲 - 这不是一个即时操作。您拥有的参数、返回地址以及其他所有内容都需要添加到递归创建的隐式堆栈中。这不会影响大O符号（好吧，如果您在真正不应该使用递归的情况下使用递归，例如在您的示例中），但实际上，会有一些（可能微小的）差异。 - IVlad

那么递归本质上就是语法糖？它如何影响我的示例（或任何示例）中的大O符号呢？在这种情况下，大O符号仍然是线性的吗？ - ordinary

@ordinary - 通常不会影响（渐近）运行时间。它可能会影响所使用的空间，就像您的示例一样。您发布的迭代实现将具有O(1)空间复杂度，而您的实现具有O（列表长度）。如果您正确使用递归和/或编译器优化尾递归，则也不会发生这种情况。 - IVlad

Answer 3

答案是否定的，例如遍历（完全）二叉树的空间复杂度为O(log N)，即树的深度。

- Aki Suihkonen

Answer 4

你是正确的。你甚至不需要变量，返回地址本身已经占用了空间。有一些方法可以避免递归中的深度嵌套（尾递归），现代编译器在许多情况下会自动执行此操作。但除此之外，从空间复杂度的角度来看，迭代将更可取。

- SomeWittyUsername