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

Question

我在考虑递归函数.采用一个简单的函数,例如一个递归打印链表:

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

起初,这似乎是一个非常无害的功能,但它不是在每个堆栈帧中存储一个地址(由变量列表标记)？假设没有尾调用优化.我们需要N个地址的空间,其中N是列表的大小.所需空间与列表大小成比例地线性增长.

我想不出如何在没有至少一个局部变量或参数存储在堆栈中的情况下实现递归函数.因此,似乎每个递归函数都具有最佳线性空间复杂度.如果是这种情况,那么在递归上使用迭代几乎总是不可取的吗？

Answer 1

虽然可以假设所有非优化函数调用都使用堆栈帧,但并非总是如此,对N个元素进行操作的递归算法将需要堆栈O(N)的大小.

递归树遍历算法使用O(lg N)堆栈帧,例如,递归QuickSort.

Answer 2

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

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

考虑深度优先遍历。您需要将每个节点以及下一个需要访问的子节点一起存储在堆栈上，以便在访问其子节点之一返回后，您知道下一个要访问哪个节点。递归使这变得非常容易，因为它抽象了所有丑陋的簿记。迭代实现不会渐近更好，而且我预计实际差异也非常非常小。

很多时候，递归使事情变得更容易，而无需牺牲任何东西。就你而言，它没有任何意义 - 这只是递归的教学示例。