递归Java – 堆栈

我正在进行递归，在这种情况下…我需要求和一个堆栈的所有值。 我有两个function，但只能使用10000条记录。 我需要一分钟。 请帮帮我！

码：

public static void main(String[] args) { Recursion r = new Recursion(); Stack 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 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 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; ），并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 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 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 stackCopy = new Stack<>(); stackCopy.addAll(stack); 

Answer 2

如果堆栈大小很大，请不要使用递归。 您将获得java.lang.StackOverflowError 。 您可以使用while循环来计算总和，如下所示：

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

Answer 3

只是想添加这个。 虽然通过迭代方式解决上述问题是更好和推荐的方法。

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

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

 public static void main(String[] args) throws InterruptedException { Stack 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)); } 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类：

 public class MyRunnable implements Runnable { private long calculatedSum; private Stack stack; public MyRunnable(Stack stack) { this.stack = stack; } @Override public void run() { calculatedSum = calculateSum(stack,0); } private long calculateSum(Stack stack2, long sum) { if (stack.isEmpty()) { return sum; } return calculateSum(stack, sum + stack.pop()); } public long getSum(){ return calculatedSum; } }