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

}