如何在递归期间将所有先前帧（较高帧）的值传递给较低帧

Question

为了简化我的问题，让我们考虑不重复地打印数组的所有排列。因此，如果 {1,2,3} 是数组，则输出如下

如何将已经属于数组的所有元素的计数传递到较低的帧。我的意思是说，在递归的前两帧中，我的堆栈中有元素 1 和 2。我需要告诉下面的框架，它可以使用除 1 和 2 之外的所有元素，因为它已经被使用了。

请参阅下面的代码，我在其中传递了所有遇到的元素的数组作为下面框架的函数调用的一部分。但是我还必须为同一帧中的其他递归调用保存和恢复数组的元素，因为 Java 不会在每个帧中保存数组的副本，并且传递引用会导致数组过度 -写了。

import java.util.Arrays;

public class SendfromHigherFrameToLowerFrame {
    static int count = 0;

    public static void main(String[] args) {
        int[] a = {1,2,3};

        int[] stack = new int[3];
        fun(a, stack, 0);

        System.out.println("count == "+count);
    }

    static void fun(int[] a, int[] stack, int frame)
    {
        if(a.length == frame)
        {
            count++;
            print(stack);
            return;
        }

        for(int i = 0;i<a.length;i++)
        {
            //save stack
            int[] temp = new int[stack.length];
            save(stack, temp);
            if(isValid(stack, a[i]) == true)
            {
                stack[frame] = a[i];
                fun(a, stack, frame+1);
                //restore stack
                restore(temp, stack);
            }
        }
    }

    static void save(int[] source, int[] destination)
    {
        for(int i = 0;i<source.length;i++)
            destination[i] = source[i];
    }

    static void restore(int[] source, int[] destination)
    {
        for(int i = 0;i<source.length;i++)
            destination[i] = source[i];
    }

    static boolean isValid(int[] a, int key)
    {
        for(int i = 0;i<a.length;i++)
        {
            if(a[i] == key)
                return false;
        }
        return true;
    }

    static void print(int[] a)
    {
        for(int x : a)
            System.out.print(x + " ");
        System.out.println();
    }
}

请提出改进代码的建议，或者更简单的方法来传递元素。

PS : 请注意，生成排列不是我最初的问题，我知道有更简单的方法可以做到这一点，这只是为了传达我的问题。

Answer 1

由于在 Java 中无法通过引用传递原语，因此您不能简单地创建一个 int，然后将其向下传递到调用堆栈中。此问题有三种解决方法：

使用可变 class，例如单个 int 或 AtomicInteger 的数组。然而，这种方法接近于滥用数组和可变 classes.
按照您的方式制作实例变量或静态变量。这远非理想，因为您的递归函数变得不可重入，因此更难测试。
Return 方法中修改后的值，add/assign 将它传递给递归方法内部的局部变量，作为它自己的 return 值传递下去。这种方法很好，但它只能容纳一个 return 值，并且需要您在编写代码时非常小心。

以下是如何修改函数以实现上述最后一种方法：

static int fun(int[] a, int[] stack, int frame) {
    if(a.length == frame) {
        print(stack);
        return 1;
    }
    int res = 0;
    for(int i = 0;i<a.length;i++) {
        //save stack
        int[] temp = new int[stack.length];
        save(stack, temp);
        if(isValid(stack, a[i]) == true) {
            stack[frame] = a[i];
            res += fun(a, stack, frame+1);
            //restore stack
            restore(temp, stack);
        }
    }
    return res;
}

Demo.

注意：不用说，你的练习不需要做任何这些，因为count总是等于stack.length。

如何在递归期间将所有先前帧（较高帧）的值传递给较低帧

How to pass a value from all previous frames (higher frames) to a lower frame during recursion

java

arrays

recursion

pass-by-reference

pass-by-value