Recursion Java - Stack

Question

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;
    }
}

Recursion one million deep is very likely to encounter a stack overflow unless you have a very large amount of memory.Note that any recursive method can be re-factored into a method that uses a single loop.. — FredK
– FredK, Commented Sep 2, 2017 at 18:21
What is the best function of recursion for this case ? @FredK — BASP
– BASP, Commented Sep 2, 2017 at 18:25
You should use the pop method of Stack instead of the weird indexing. — luk2302
– luk2302, Commented Sep 2, 2017 at 18:38

yassadi · Accepted Answer · 2018-05-12 07:31:31Z

1

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; 
}

edited May 12, 2018 at 7:31

yassadi

5241 gold badge9 silver badges20 bronze badges

answered Sep 2, 2017 at 18:44

Anoop Kumar

4881 gold badge8 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

c0der · Accepted Answer · 2017-09-03 11:59:17Z

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);

Roshan · Accepted Answer · 2017-09-02 20:43:34Z

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;
    }

}

Collectives™ on Stack Overflow

Recursion Java - Stack

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related