java - 尝试递归打印整数 LinkedList 时出现堆栈溢出错误？ ( java )

Question

解决一个问题，我使用了两种方法(迭代和递归)来遍历链接列表，然后比较每种方法完成所需的时间。

我正在尝试打印一个链接列表，其中包含指定范围(从 0-1000000)内的任意整数(从 0-99)，但是当我尝试使用 printRecursively 函数时，出现堆栈溢出错误递归打印列表中的数字。我的迭代工作正常，但我不明白为什么当我使用其他方法时我不断收到堆栈溢出错误。帮助？谢谢

public class Compare {

/**
 * @param args the command line arguments
 */


public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.println("Please enter the number of integers you wish to have inside the LinkedList:");
    Integer numberOfItems = input.nextInt();
    while (numberOfItems > 1000000 || numberOfItems < 0){
        System.out.println("Not valid number. Please re-enter a valid integer:");
        numberOfItems = input.nextInt();
    }

    LinkedList<Integer> list = new LinkedList<Integer>();

    int i = 0;
    Random rand = new Random();
    while(i < numberOfItems){
    int randomNumber = rand.nextInt(99);
    list.add(i, randomNumber);
    i++;
    }

    System.out.println("Would you like to print iteratively or recursively? (Type i or r):");
    char choice = input.next().charAt(0);
    if (choice != 'i' && choice != 'r')
    {        
        int h = 0;
        while(h == 0){ 
        System.out.println("Incorrect input. (Type i or r):");
        choice = input.next().charAt(0);
        if (choice == 'i' || choice == 'r'){
            h = 1;               
        }
        }
    }     

    if (choice == 'i'){
        double startTime = System.nanoTime();
        Functions blah = new Functions();
        blah.printIteratively(list);
        double endTime = System.nanoTime();
        double duration = ((endTime - startTime)/1000000000);
        System.out.println("The method took " + duration + " seconds to complete.");
        }

    if (choice == 'r'){
        double startTime = System.nanoTime();
        Functions blah = new Functions();       
        blah.printRecursively(list);
        double endTime = System.nanoTime();
        double duration = ((endTime - startTime)/1000000000);
        System.out.println("The method took " + duration + " seconds to complete.");
        } 
    }

}

这是我的功能:

public void printIteratively(LinkedList<Integer> list)
{  
     int k = list.size();
     for(int j = 0; j < k; j++){
        System.out.println(list.get(j));
    }
}
public void printRecursively(LinkedList<Integer> list)
{
    while(!(list.peek() == null)){  
    System.out.println(list.pollLast());
    printRecursively(list);
     }
}

}

Answer 1

简单的答案是，递归是用于迭代列表内容的错误工具。这是一种迭代顺序算法，当列表变得太大时，递归将会失败。这不是调整递归算法的问题，它只是错误的，并且对于足够大的列表总是会失败，而简单的迭代将继续正常工作。

递归失败的具体原因是每个递归调用都会消耗一个堆栈帧的内存，其中包括一些内务信息和方法中所有局部变量的实例。最终你会耗尽堆栈空间，从而导致 StackOverflow 异常。

递归解决方案始终对它可以处理的列表大小有一个上限，这几乎肯定比您可以存储在内存中的列表大小小很多。您可以通过分配更多堆栈空间(使用 -Xss 命令行选项)来增加限制，但限制基本上是算法的一部分，也是 Java 等语言中递归工作方式的一部分。

如果您有兴趣，请查找术语“尾递归”。在某些语言中，编译器(或解释器)会检测到这一点并将其转换为迭代(我认为 Lisp 会这样做)。