3

For this assignment given to me, I am supposed to move through a linked list of size 1,000,000 iteratively and recursively. I have the iterative part down but I am confused on the recursive part. I have the concept down but I have told my teacher that I cannot recursively do it because I will inevitably get a stack overflow error. He says I should not be getting that problem but I am totally stuck. Any tips would be great as I have no idea what I am doing wrong.

public static void main(String[] args) {
 System.out.println("Please enter how many random numbers you want to generate: ");
 Scanner prompt = new Scanner(System.in);
 int amount = prompt.nextInt();
 Random rnd = new Random();
 System.out.println("Creating list...");
 for (int i = 0; i < amount; i++) {
 randomList.add(rnd.nextInt(100));
 }
 System.out.println("Going through list...");
 iterateNumbers();
 long startTimeRec = System.nanoTime();
 recursiveNumbers(randomList);
 long elapsedTimeRec = System.nanoTime() - startTimeRec;
 double seconds = (double)elapsedTimeRec / 1000000000.0;
 System.out.println("Recursively, the function took " + seconds + " seconds.");
 prompt.close();
}
//create the linked list
public static LinkedList<Integer> randomList = new LinkedList<Integer>();
private static void iterateNumbers() {
 long startTime = System.nanoTime();
 for (int i = 0; i < randomList.size(); i++) {
 randomList.remove();
 }
 long elapsedTime = System.nanoTime() - startTime;
 double seconds = (double)elapsedTime / 1000000000.0;
 System.out.println("Iteratively, the function took " + seconds + " seconds.");
}
private static void recursiveNumbers(LinkedList<Integer> current) { 
 if (current.isEmpty() == true) {
 return;
 } else {
 current.removeFirst();
 recursiveNumbers(current);
 }
}
}
BenMorel
36.9k52 gold badges208 silver badges339 bronze badges
asked Mar 25, 2014 at 1:27
1
  • What did you get with this code? What is your exact question? Commented Mar 25, 2014 at 1:50

2 Answers 2

1

It's not very hard to understand. When you run your program, the stack area is not enough,so you have a error.

You can try to add the space of the stack.

run the program with the following arguments:

-Xss1280m

It means create the stack with 1280MB, and you will see the result like this:

enter image description here

answered Mar 25, 2014 at 1:52
8
  • 1
    how would i go about running my program with those arguments? is it possible to make that statement within my code so it would automatically allocate a greater stack area for anyone who runs the program? Commented Mar 25, 2014 at 1:59
  • 1
    You can compile the java file first with the code javac Main.java, and run with the code:java -Xss1280m Main.And I write the shell script to run the program instead of run it directly.Here is my script:java -Xss1280m Main,and I just run with sh run.sh,and it works.If you are in windows, you can also write the .bat file. Commented Mar 25, 2014 at 2:10
  • okay I gotcha, but is there any way to write in my .java file to create a stack with 1280MB? Commented Mar 25, 2014 at 2:17
  • 1
    I am not sure whether there is any way we can do that.But what I see is a script with a config file until now. Commented Mar 25, 2014 at 2:24
  • 1
    @Arkant0r: I think it is not possible to specify the stack size from the java source code because it would be a security risk. Commented Mar 25, 2014 at 2:57
1

In the iterative version , you should pass in the index at the remove.

randomList.remove(i);

And should you not also repopulate the linked list before you call the recursive method?

 for (int i = 0; i < amount; i++) {
 randomList.add(rnd.nextInt(100));
}

Not too sure about the Java implementation of the Linked List. Tried looking it up there. Is there a isEmpty() method? Or should you try:

if(current.size() < 1) 
 return;
answered Mar 25, 2014 at 1:42
2
  • you're right I forgot to repopulate the list! Let me get back to you once i try that. Commented Mar 25, 2014 at 1:51
  • Well I repopulated the list and passed the index at the remove statement but I'm still getting a stackoverflowerror when I create a linked list with 1,000,000 integers and then use the recursive function. Commented Mar 25, 2014 at 1:56

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.