Recursion Java - Stack

Question

Je travaille sur la récursivité, dans ce cas ... J'ai besoin de sommer toutes les valeurs d'une pile. J'ai deux fonctions, mais ne fonctionne qu'avec 10000 enregistrements. J'ai besoin d'un millier. Aidez-moi, s'il vous plaît!

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

Answer 1

Si vous devez avoir une solution récursive (car bien sûr, ou toute autre exigence), mais comme expliqué ici, il n'est pas optimale, vous pouvez le faire en limitant la profondeur de récursivité.
L'idée est de limiter la profondeur de récurrence (RECURRSION_DEPTH = 1000;), et de sommer la pile pièce par pièce. Cela permet d'additionner une pile de n'importe quelle taille. Dans l'exemple suivant, la taille est de 1 M (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; 
     } 
    } 
} 

On notera que, à la fin de la course de récursivité, la pile est vide . Si ce n'est pas acceptable, vous pouvez toujours faire la somme sur une copie:

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

Answer 2

Ne pas utiliser récursivité si la taille de la pile est énorme. Vous obtiendrez java.lang.StackOverflowError. Vous pouvez utiliser la boucle while pour calculer la somme.

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

    return sum; 
} 

Answer 3

Juste en pensant d'ajouter ceci. Bien qu'il soit préférable et recommandé de résoudre le problème ci-dessus de manière itérative.

Il y a encore une autre façon de le résoudre. Une façon consiste à augmenter la taille de la pile JVM. L'autre façon est d'augmenter la taille de la pile par programme lors de la création de threads.

Ici, je donne un exemple pour l'augmenter par programmation.

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 Classe:

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

}