Recursion Java - Stack

问题:

I am working on recursion, in this case... I need sum all values of one stack. I have two functions, but only work with 10000 records. I need min one millon. Help me, please!

Code:

public static void main(String[] args) {
    Recursion r = new Recursion();
    Stack<Integer> stack = new Stack();
    Random rnd = new Random();
    int stack_size = 10000;
    for (int i = 0; i < stack_size; i++) {
        stack.push(rnd.nextInt(10 - 1));
    }
    int s = r.stack2(stack, 0);
    //int s = r.stack1(stack, stack_size, 0, 0);
    System.out.println("Sum = " + s);
}

public int stack2(Stack<Integer> stack, int sum) {
    if (stack.size() > 1) {
        sum += (stack.get(0) + stack.get(1));
        stack.remove(stack.get(0));
        stack.remove(stack.get(0));
        return stack2(stack, sum);
    } else {
        return sum;
    }
}

public int stack1(Stack<Integer> stack, int size, int i, int sum) {
    if (i < size) {
        i++;
        sum = sum + stack.get(i - 1);
        return stack1(stack, size, i, sum);
    } else {
        return sum;
    }
}

回答1:

If you must have a recursive solution (because of course or any other requirement), although as explained here it is not optimal, you can do so by limiting the recursion depth.
The idea is to limit the recursion depth (RECURRSION_DEPTH = 1000;) , and sum the stack piece by piece.
Doing so you can sum a stack of any size. In the following example the size is 1M (STACK_SIZE = 1000000;):

import java.util.Random;
import java.util.Stack;

public class StackRecursionSum  {

    private final static int STACK_SIZE = 1000000;
    private final static int RECURRSION_DEPTH = 1000; //limit of the recursion depth 

    public static void main(String[] args) {

        StackRecursionSum r = new StackRecursionSum();

        Stack<Integer> stack = new Stack<>();
        Random rnd = new Random();

        for (int i = 0; i < STACK_SIZE; i++) {
            stack.push(rnd.nextInt(10 - 1));
        }

        int sumForTesting =0;
        for (int i = 0; i < STACK_SIZE; i++) {
             sumForTesting += stack.get(i);
        }

        int stackSum = 0;
        while(! stack.isEmpty()) {

            stackSum += r.sumStack(stack, RECURRSION_DEPTH, 0);
        }

        //output
        System.out.println("Stack sum is = " + stackSum);

        //test 
        if(! stack.isEmpty()) {

            System.out.println("Error: stack is not empty. Recurssion did not end properly");
        }else if (stackSum != sumForTesting){

            System.out.println("Error: wrong test sum. Should be "+ sumForTesting);
        }else {
            System.out.println("************** All ok ");
        }
    }

    private int sumStack(Stack<Integer> stack, int maxNumberOfElementsToSum,  int sum) {

        if ((maxNumberOfElementsToSum > 0) && ! stack.isEmpty()) {

            maxNumberOfElementsToSum --;
            sum += stack.pop(); //remove last element from stack and add to sum

            return sumStack(stack, maxNumberOfElementsToSum , sum);

        } else {

            return sum;
        }
    }
}

Note that at the end of the recursion run, the stack is empty. If this is not acceptable, you can always do the summation on a copy :

    Stack<Integer> stackCopy = new Stack<>();
    stackCopy.addAll(stack);

回答2:

Don't use recursion if stack size is huge. You will get java.lang.StackOverflowError. You can use while loop to calculate sum like this:

public int stack2(Stack<Integer> stack) {
    int sum = 0;
    while (!stack.isEmpty()) {
        sum += stack.pop();
    }

    return sum; 
}

回答3:

Just thinking to add this. Although it is better and recommended way to solve the above problem by Iterative way.

There is yet another way we can solve it . One way is to increase JVM stack size. Other way is to increase stack size programatically while creating thread.

Here I am giving an example to increase it programatically.

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

        Stack<Integer> stack = new Stack<Integer>();
        Random rnd = new Random();
        int stack_size = 10000;
        for (int i = 0; i < stack_size; i++) {
            stack.push(rnd.nextInt(10 - 1));
        }

        MyRunnable r = new MyRunnable(stack);

        Thread t = new Thread(null, r, "test-thread",  1 << 23);
        t.start();
        t.join();
        System.out.println(r.getSum());    
    }

Runnable Class:

public class MyRunnable implements Runnable {

    private long calculatedSum;
    private Stack<Integer> stack;


    public MyRunnable(Stack<Integer> stack) {
        this.stack = stack;
    }

    @Override
    public void run() {
        calculatedSum = calculateSum(stack,0);
    }

    private long calculateSum(Stack<Integer> stack2, long sum) {
        if (stack.isEmpty()) {
            return sum;
        }
        return calculateSum(stack, sum + stack.pop());
    }


    public long getSum(){
        return calculatedSum;
    }

}