递归使用多少堆栈（从列表中删除节点）？

Question

更新：请注意，就目前而言，这个问题没有多大意义，因为调用堆栈将独立于类型 T 增长。调用堆栈仅取决于节点数在正在处理的列表中 - 这些节点中包含的数据对调用堆栈的大小没有影响。

假设我有一个 "remove-node-from-list" 方法的递归 java 实现，看起来像这样：

// head
public void remove(T data) {
    if (data == null)
        throw new IllegalArgumentException();
    head = remove(head, data);
}

// other nodes of list
private ListNode remove(ListNode current, T data) {
    if (current == null)
        return null;
    if (current.data.compareTo(data) == 0)
        return current.next;
    current.next = remove(current.next, data);
    return current;
}

让我们进一步假设类型 T 是 int

我的问题是： 与我正在处理的列表的大小相比，调用堆栈（在最坏的情况下）会有多大？

到目前为止我的想法： 据我所见，Java 8 没有优化递归（对吗？我的整个分析都假设这是真的）。因此，我们将有一个随列表大小线性增长的调用堆栈。

更准确地说：此方法remove(ListNode current, T data) 基本上会在每个节点的调用堆栈上放置一个节点引用（32 位在 32 位架构上）和一个 int（也是 32 位）在我的列表中。

现在，由于列表中的一个节点也由一个引用和一个 int 组成，因此该节点实际上与其中一个递归调用的大小几乎相同。实际上，其中一个调用甚至可能使用更多 space（return 地址也必须压入堆栈，对吗？或者可以通过某种方式优化掉它吗？）。

因此，如果我是正确的，那么在最坏的情况下（当要删除的元素是列表中的最后一个元素时），调用堆栈基本上会变得和列表本身一样大！真的是这样吗？如果我是正确的，那么这意味着处理 int 列表所需的调用堆栈的系数为 1 甚至更大！因此，在处理大型列表（实际上甚至没有那么大）时，假设 1M 一个人如果使用默认设置 stacksize (0.5M)

运行就会得到一个 Whosebug

我知道这样一个事实，即对于更大的数据类型，这个因素会更小，但在任何情况下我仍然坚持的基本上是这样的：如果没有进行优化，那么调用堆栈将随着列表的大小线性增长 - 因此人们应该更喜欢迭代而不是递归过程。

通常我会说，调用堆栈将大致以一个因子 (size_of_all_arguments_in_call + size_of_return_address)/size_of_a_single_listelement 线性增长，在 int 列表的情况下几乎是一样的，对吧？请不要误会 size_of_all_arguments 的意思：我知道我们只将引用的值传递给这些调用中的对象，而不是整个对象本身。因此，对于大型对象，该因素可能不会那么显着，但我仍然认为人们不应该接受不必要的线性 space-开销。但是，对于 int 的列表，该因子约为。 1.

这个分析是正确的还是我遗漏了什么？

背景：与我讨论此事的人试图说服我 java 中的调用堆栈不会增长得如此剧烈，并指出我失踪了一些明显的东西（不幸的是没能告诉我什么，对我来说它真的一点也不明显）——因为我不知道它是什么我想念我渴望学习；）

相关：

Recursive vs. Iterative algorithms
Recursion or iteration?
Is recursion ever faster than looping?

对我来说，相关问题中缺少的主要内容是调用堆栈实际使用多少space

Answer 1

How much stack does a recursion use (removing node from list)?

如果不分析代码或了解特定 JVM 的细节，这是一个很难回答的问题。那是因为 Java Virtual Machine Specification (JVMS) 将许多细节留给了实现者。

JVMS Chapter 2: Implementation details that are not part of the Java Virtual Machine's specification would unnecessarily constrain the creativity of implementors. For example, the memory layout of run-time data areas, the garbage-collection algorithm used, and any internal optimization of the Java Virtual Machine instructions (for example, translating them into machine code) are left to the discretion of the implementor.

这些细节的一部分是堆栈和堆栈框架实现。而且由于您似乎实际上是在询问递归删除创建的堆栈与算法正在处理的列表之间的关系，因此我们必须考虑堆栈帧在堆栈上的大小甚至可能没有您想象的那么大（或在你的问题中提出。

JVMS (§2.5.2): Because the Java Virtual Machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated.

这意味着每个堆栈帧只能将一个引用放入堆栈。如果是这样，那将使堆栈和它正在处理的列表之间的关系对于您提供的示例来说真的无关紧要。让我们看一些数字：

根据Algorithms (Sedgewick, Wayne)：

一个Integer是24字节
开销+实例变量（int）+填充
= 16 + 4 + 4 = 24 字节
一个非静态的递归定义Node class嵌套在关联 List 是 40 个字节 开销+引用+额外开销（引用Listclass）
= 16 + 8 + 8 + 8 = 40 字节

因此，我们可以看到列表中每个条目有 64 个字节。因此，如果有一个框架是堆分配的实现，则堆栈和您正在处理的列表之间的关系将是 8/64 = 1/8 bytes.

当栈帧在栈上分配时，更难确定栈的大小。事实上，我们需要进一步的实施细节来确定它。

JVMS (§2.6. Frames): The sizes of the local variable array and the operand stack are determined at compile-time and are supplied along with the code for the method associated with the frame (§4.7.3). Thus the size of the frame data structure depends only on the implementation of the Java Virtual Machine, and the memory for these structures can be allocated simultaneously on method invocation.

即便如此，我想说的是，以您的示例为例，相对于列表（此处谈论内存中的总大小），堆栈不太可能增长到或接近 1:1。当然，您可以提出一个特定的问题来验证您的论点，但它可能是微不足道的，并且可能不适用于您提供的示例。

递归使用多少堆栈（从列表中删除节点）？

How much stack does a recursion use (removing node from list)?

java

stack-overflow

recursion

linked-list

list