Stack overflow error when attempting to print out LinkedList of integers recursively? (Java)

Question

Working through a problem where I made two methods, iterative and recursive, for going through a Linked List then comparing how long it took for each to complete.

I'm trying to print an Linked List of that contains as many random integers (From 0-99) in a specified range (from 0-1000000) but I get a Stack Overflow error when I attempt to use my printRecursively function to print out the numbers of the list recursively. My iterative one works fine but I can't figure out why I keep getting a Stack Overflow error when I use my other method. Help? Thank you

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.");
        } 
    }

}

And here's my functions:

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

The simple answer is that recursion is the wrong tool to use for iterating over the contents of a list. That is an iterative sequential algorithm and recursion will fail when the list gets too big. It's not a question of adjusting the recursive algorithm, it's just wrong and will always fail for a large enough list, where simple iteration would continue to work just fine.

The specific reason recursion fails is that each recursive call consumes a stack frame's worth of memory, which includes some housekeeping information and instances of all local variables in the method. Eventually you run out of stack space, which results in a StackOverflow exception.

The recursive solution will always have an upper limit to the size of list it can handle which will almost surely be a lot smaller than the size of list you can store in memory. You can increase the limit by allocating more stack space (using the -Xss command line option), but the limit is fundamentally part of the algorithm and the way recursion works in languages like Java.

If you are interested, look up the term "tail recursion". There are some languages where the compiler (or interpreter) will detect this and convert it to iteration (I think Lisp does this).