递归Java - 堆栈

Question

我正在处理递归，在这种情况下...我需要总和一个堆栈的所有值。 我有两个功能，但只能使用10000条记录。我需要一分钟。请帮帮我！

代码：

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

Answer 1

如果你必须有（因为课程或任何其他规定的）递归解决方案，虽然这里解释它是不是最佳的，你可以通过限制这样做递归深度。
这个想法是限制递归深度（RECURRSION_DEPTH = 1000;），并一块一块地累加堆栈。
这样做可以将任意大小的堆栈合计在一起。在以下示例中的大小为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; 
     } 
    } 
} 

注意，在递归运行结束，堆栈空。 如果这是不可接受的，你总是可以做一个副本的总和：

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

Answer 2

如果堆栈大小是巨大的，不要使用递归。你将得到java.lang.StackOverflowError。您可以使用while循环来计算总和。

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

    return sum; 
} 

Answer 3

只是想补充一点。尽管通过迭代方式解决上述问题是更好的选择和推荐的方法。

还有另一种方法可以解决它。一种方法是增加JVM堆栈大小。其他方法是在创建线程时以编程方式增加堆栈大小。

这里我举一个例子来以编程方式增加它。

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

运行的类：

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

}