java - 递归Java

我正在进行递归，在这种情况下...我需要对一个堆栈的所有值求和。
我有两个功能，但只能处理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;
    }
}

最佳答案

如果您必须具有递归解决方案（当然是由于其他原因或其他要求），尽管如此处所述，它不是最佳解决方案，但可以通过限制递归深度来实现。
这个想法是要限制递归深度（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);

关于java - 递归Java，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46016822/