recursion - 什么会影响递归中的堆栈大小？

Question

递归方法调用的具体哪些部分对堆栈有贡献——比如返回的对象、参数、局部变量等？

我正在尝试优化 Android 应用程序在遇到 StackOverflowException 之前可以在有限内存上执行的递归级别。

提前致谢。

Answer 1

如果堆栈空间不足，请不要优化堆栈使用。这样做只是意味着同样的问题稍后会再次出现，输入集稍大或从其他地方调用。在某些时候，您已经达到了可以用于解决问题的理论或实际最小空间。相反，将有问题的代码转换为使用机器堆栈以外的集合（例如，堆分配的堆栈或队列）。这样做有时会导致代码非常难看，但至少不会崩溃。

但是要回答这个问题：通常，您命名的所有内容都可以占用堆栈空间，而临时值也占用空间（因此疯狂地嵌套表达式只是为了保存局部变量将无济于事）。其中一些将存储在寄存器中，具体取决于调用约定，但无论如何可能都必须被溢出（*）。但是不管调用约定如何，这只会为您节省几个字节，并且由于被调用者通常在调用期间可以自由支配寄存器，因此调用时必须溢出所有内容。因此，当您的堆栈溢出时，堆栈确实挤满了参数、局部变量和早期调用的临时变量。如果同时不需要它们，一些可能会被完全优化掉或共享一个堆栈槽。最终这取决于 JIT 编译器。

(*) 溢出：将值从寄存器移动到内存（即堆栈），因为其他东西需要寄存器。

Answer 2

每个方法都有两个与之关联的堆栈帧大小，参数和局部变量所需的堆栈，以及表达式求值所需的堆栈。返回值仅计为表达式评估所需的堆栈的一部分。JVM 能够验证方法在执行时不超过这些大小。

变量和表达式评估究竟需要多少堆栈取决于字节码编译器。例如，它通常能够在具有非重叠生命周期的变量之间共享局部变量槽。