saltandwater saltandwater - 4 months ago 8
Java Question

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

To simplify asking my question, let us consider printing all permutations of an array, without repetition. So if {1,2,3} was the array, the output would be the following

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


How can I pass a count of all the elements that are already part of the array to a frame lower. I mean, say, in the first two frames of recursion, I have elements 1 and 2 in my stack. I need to tell the frame below, that it can use all elements except for 1 and 2, since it's already used.

Please see my code below, where I pass an array of all encountered elements as part of the function call for the frame below. But I also have to save and restore the elements of the array for other recursive calls in the same frame, since Java does not save a copy of the array in each frame, and passing references causes the Array to get over-written.

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


Please suggest improvements to the code, or an easier way for passing elements down the call.

PS : Please note that generating permutations is not my original question, and I understand there are simpler ways to do it, it's solely for the purpose of conveying my question.

Answer

Since there is no way to keep passing a primitive by reference in Java, you cannot simply make an int, and pass it down the invocation stack. There are three work-arounds to this issue:

  • Use a mutable class, such as an array of a single int, or AtomicInteger. This approach, however, borders on a misuse of arrays and mutable classes.
  • Make an instance variable or a static variable, the way you did it. This is far from ideal, because your recursive function becomes non re-entrant, and so it is much harder to test.
  • Return the modified value from the method, and add/assign it to a local variable inside the recursive method to pass down as its own return value. This approach is good, but it accommodates only a single return value, and requires you to be very careful when writing your code.

Here is how you function can be modified to implement the last approach described above:

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.

Note: It goes without saying that your exercise does not need to do any of that, because count is always equal to stack.length.

Comments