评估树遍历递归算法(Java)中是否可能发生堆栈溢出错误 [英] Evaluating if a stack overflow error is possible in a tree traversal recursive algorithm (Java)

问题描述

从理论上(即不实际执行)确定某个树遍历递归算法将在Java中产生堆栈溢出的情况的最佳方法是什么?

What is the best way to determine theoretically (i.e., without actually executing it) the circumstances in which a certain tree traversal recursive algorithm will produce a stack overflow in Java?

为了阐明我的问题，请考虑以下示例. 给定一个用Java实现的简单二叉树:

In order to clarify my question, consider the following example. Given a simple binary tree implemented in Java:

public class Node {
    private int value;
    private Node left;
    private Node right;
    ...

    //in-order traversal
    public void inOrder() {
        if (left != null) {
            left.inOrder();
        }
        System.out.println(value);
        if (right != null) {
            right.inOrder();
        }
    }
}

在此算法中，嵌套递归调用的最大数量相对于树的深度是线性的. 那么，如何估计树的最大深度，该深度将允许顺序遍历算法(或类似方法)完成而不会引发堆栈溢出错误?

In this algorithm, the maximum number of nested recursive calls is linear with respect to the depth of the tree. So how can I estimate which is the maximum depth of the tree that will allow an in-order traversal algorithm (or similar) to complete without throwing a stack overflow error?

如果最大堆栈大小是通过-Xss选项，将这个数字除以我的递归算法所使用的每个堆栈帧的估计值是否正确?

If the maximum stack size is assigned by thread by means of the -Xss option, is it correct to just divide this number to an estimation of each stack frame used by my recursive algorithm?

通过将参数和局部变量的大小添加到程序计数器的大小来估计每个堆栈帧的大小是否正确，其中程序计数器的大小取决于体系结构(32位对64位，依此类推). ..).

And is it correct to estimate the size of each stack frame by adding the size of parameters and local variables to the size of the program counter, where the program counter size depends on the architecture (32 bits vs 64 bits, etc...).

我还想念其他东西吗?

更新:

我确实知道可以将递归算法转换为迭代算法，以避免堆栈溢出错误.这只是关于递归算法的理论问题.

I do know that a recursive algorithm can be converted to an iterative one in order to avoid stack overflow errors. This is just a theoretical question regarding recursive algorithms.

推荐答案

我了解这主要是理论问题，但这是有效的问题.您的估计正确.除了堆栈转到Xms，而局部变量转到Xmx.因此，根据实际数据，每次迭代所使用的内容以及树的可用RAM深度的实际大小实际上会有所不同.

I understand that this is mostly theoretical question but it is valid question. You are right in your estimates. Except stack goes to Xms but local variables go to Xmx. So, based on real data what you use on each iteration and real size of available RAM depth of tree really varies.

这篇关于评估树遍历递归算法(Java)中是否可能发生堆栈溢出错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！