何时使用递归：哪些重要因素决定何时发生堆栈溢出？ [复制]

Question

此问题已经在这里有了答案：

• What is the maximum depth of the java call stack?4个答案

我最近编写了一些实验代码，将一种简单的递归算法与另一种简单的for循环方法进行比较，以便在数组列表中查找数字。这可能不是递归大放异彩的最佳示例。另外，到目前为止，我知道二进制搜索通常比线性搜索更有效。但是，这只是一个随机实验，我的问题来自尝试它。这是实验的一些结果：

 * ArrayList of size 1,000, find 890:
 * The number was found in 0 milliseconds using a for loop.
 * The number was found in 1 milliseconds using a recursive loop.
 * 
 * ArrayList of size 10,000, find 7,000:
 * The number was found in 1 milliseconds using a for loop.
 * The number was found in 2 milliseconds using a recursive loop.
 * 
 * ArrayList of size 10,000, find 8,900:
 * The number was found in 2 milliseconds using a for loop.
 * Exception in thread "main" java.lang.StackOverflowError
 * 
 * ArrayList of size 100,000, find 99,999:
 * The number was found in 6 milliseconds using a loop.
 * Exception in thread "main" java.lang.StackOverflowError
 * 
 * ArrayList of size 1,000,000, find 999,999:
 * The number was found in 12 milliseconds using a loop.
 * Exception in thread "main" java.lang.StackOverflowError

现在，我的问题：如果您查看使用不同列表大小运行上述代码的一些结果，您可能会注意到，当我开始在数组列表中搜索大于7,000的数字时，大于等于10,000的大小时，会发生堆栈溢出。

我确实知道，递归函数将在每次递归调用函数时将堆栈帧推入堆栈，这可能导致堆栈溢出。但是，我很想知道，例如：

• 什么决定了堆栈的大小？
• 在较慢的计算机上，如果堆栈数低于7,000，是否会发生堆栈溢出？] >>
• 考虑到这些因素，有没有一种方法可以计算或估算何时可能发生堆栈溢出？

我希望这些是有效的问题。

这是我的代码：

import java.util.ArrayList;

public class RecursionExperiment {

    public static void main(String[] args) {
        long startTime;
        long runTime;
        boolean numWasFound;
        String numFoundString;

        ArrayList<Integer> numList = new ArrayList<Integer>();
        fillArrayList(numList, 1, 1000000);

        int numToFind = 999999;

        startTime = System.currentTimeMillis();
        numWasFound = isNumInList(numList, numToFind);
        runTime = System.currentTimeMillis() - startTime;
        numFoundString = numWasFound ? "was found" : "was not found";
        System.out.println("The number " + numFoundString + " in " + runTime + 
                " milliseconds using a for loop.");

        startTime = System.currentTimeMillis();
        numWasFound = isNumInListRecurse(numList, 0, numToFind);
        runTime = System.currentTimeMillis() - startTime;
        numFoundString = numWasFound ? "was found" : "was not found";
        System.out.println("The number " + numFoundString + " in " + runTime + 
                " milliseconds using a recursive loop.");
    }

    static boolean isNumInList(ArrayList<Integer> list, int numToFind) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == numToFind) {
                return true;
            }
        }
        return false;
    }

    static boolean isNumInListRecurse(ArrayList<Integer> list, int index, int numToFind) {
        if (index == list.size()) {
            return false;
        }
        return list.get(index) == numToFind || isNumInListRecurse(list, ++index, numToFind);
    }

    static ArrayList<Integer> fillArrayList(ArrayList<Integer> arrayList, int from, int to) {
        for (int i = from; i <= to; i++) {
            arrayList.add(i);
        }
        return arrayList;
    }

}
我必须承认，我在这些问题上的功课还不够充分，如果我的问题还差一点，请原谅我。预先感谢您的帮助。

我最近编写了一些实验代码，将一种简单的递归算法与另一种简单的for循环方法进行比较，以便在数组列表中查找数字。这可能不是...

Answer 1

首先决定堆栈大小的是什么？