java - 如何在递归期间将值从所有先前帧(较高帧)传递到较低帧

Question

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

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
count == 6

如何将已经属于数组的所有元素的计数传递给较低的框架。我的意思是，在递归的前两帧中，我的堆栈中有元素 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，并将其传递到调用堆栈中。此问题有三种解决方法:

• 使用可变类，例如单个 int 的数组，或 AtomicInteger 。然而，这种方法接近于滥用数组和可变类。
• 按照您的方式创建一个实例变量或静态变量。这远非理想，因为您的递归函数变得不可重入，因此测试起来更加困难。
• 从方法中返回修改后的值，并将其添加/分配给递归方法内的局部变量，以作为其自己的返回值向下传递。这种方法很好，但它只容纳单个返回值，并且要求您在编写代码时非常小心。

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

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。