递归Java - 代码日志 [英] Recursion Java - Stack

问题描述

我正在研究递归，在这种情况下...我需要对一个堆栈的所有值求和.我有两个函数，但只能处理 10000 条记录.我需要至少一百万.请帮帮我！

I am working on recursion, in this case... I need sum all values of one stack. I have two functions, but only work with 10000 records. I need min one millon. Help me, please!

代码:

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;):

If you must have a recursive solution (because of course or any other requirement), although as explained here it is not optimal, you can do so by limiting the recursion depth.
The idea is to limit the recursion depth (RECURRSION_DEPTH = 1000;) , and sum the stack piece by piece.
Doing so you can sum a stack of any size. In the following example the size is 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;
        }
    }
}

请注意，在递归运行结束时，堆栈空.如果这是不可接受的，您可以随时对副本进行求和:

Note that at the end of the recursion run, the stack is empty. If this is not acceptable, you can always do the summation on a copy :

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

这篇关于递归Java - 代码日志的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！