java - 如何避免Java中递归调用次数多导致的StackOverflowError？

Question

我想解决这个问题:https://www.hackerrank.com/challenges/find-median ，IE。在未排序的数组中找到中值元素。为此，我执行快速选择算法。

我的程序在我的电脑上运行正常。但是，当我在系统中提交时，它给了我 StackOverflowError。我认为这是因为递归调用的深度。我想我进行了太多的递归调用，超出了 Java 允许的范围(错误是由具有 10 001 个数字的测试用例引起的)。有人可以建议我如何避免这种情况吗？

这是我的代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class FindMedian {
    static int res;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String line1 = br.readLine();
        int N = Integer.parseInt(line1);
        String[] line2 = br.readLine().split(" ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(line2[i]);
        }
        selectKth(arr, 0, N - 1);
        System.out.println(res);
    }

    public static void selectKth(int[] arr, int start, int end) { 
        // it is written to select K-th element but actually
        // it selects the median element
        if (start >= end) {
            res = arr[start];
            return;
        }
        int pivot = arr[start];
        int n = arr.length - 1;
        int i = start + 1;
        int j = end;
        while (i <= j) {
            while (arr[i] <= pivot) {
                i++;
            }
            while (pivot < arr[j]) {
                j--;
            }
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        int tmp = arr[j];

        // j is the index of the last element which is bigger or equal to pivot
        arr[j] = pivot;

        arr[start] = tmp;
        if (n / 2 <= j) {
            selectKth(arr, start, j);
        } else {
            selectKth(arr, i, end);
        }
    }
}

Answer 1

IT 科学的一个基本概念是用迭代代替递归。通过使用迭代，您永远不会遇到“递归太深”的错误。每个问题都可以通过递归或迭代来解决。

有关详细信息，请参阅我的链接。 http://www.refactoring.com/catalog/replaceRecursionWithIteration.html