CODEWITHSUNDEEP
loopspass-by-value
Anurag
Anurag

Reputation: 733

Java variable not retaining value outside loop

I am going through a sample Java code to

print all possible permutations of a given String (with duplicates included)

.

Here is the code:

public class StringPermutationWithRepetition {

    public static void main(String[] args) {
        String dictionary = "ABC";
        printPermutation(dictionary, "");

    }

    public static void printPermutation(String str, String stringToPrint) {
        System.out.println("The permutation now is: "+stringToPrint);

        if (str.length() == stringToPrint.length()) {
            System.out.println(stringToPrint);
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            printPermutation(str, stringToPrint + str.charAt(i));
        }
    }

}

Here is a part of the output:

The permutation now is: 
The permutation now is: A
The permutation now is: AA
The permutation now is: AAA
AAA
The permutation now is: AAB
AAB
The permutation now is: AAC
AAC
The permutation now is: AB
The permutation now is: ABA
ABA

Problem: I am not able to understand this part of the output:

The permutation now is: AAA
    AAA
    The permutation now is: AAB
    AAB

i.e. at the instance when stringToPrint = 'AA' and str.charAt(i) = 'A'

and a recursive call is made to the function again:

printPermutation(str, stringToPrint + str.charAt(i));

The output is:

The permutation now is: AAA
        AAA

and the stringToPrint = 'AAA'

but as soon as the return is encountered and the loop begins again:

return;
        }

        for (int i = 0; i < str.length(); i++) {
            printPermutation(str, stringToPrint + str.charAt(i));
        }

The value of stringToPrint falls back to 'AA'. Why is that?

I have a intuition that this is somewhere related to Java being Pass by value and not Pass by reference.

Upvotes: 0

Views: 142

Answers (2)

libik
libik

Reputation: 23029

You probably misunderstanding recursion. In this case it works similar to "DFS", it enters the first solution possible. When there is no solution it goes one step back.

printPermutation("ABC","")
---> printPermutation("ABC","A")
     ---> printPermutation("ABC","AA")
          ---> printPermutation("ABC","AAA")
               ---> (str.length() == stringToPrint.length()); //ends
          ---> printPermutation("ABC","AAB")
               ---> (str.length() == stringToPrint.length()); //ends
          ---> printPermutation("ABC","AAC")
               ---> (str.length() == stringToPrint.length()); //ends
     ---> printPermutation("ABC","AB")
          ---> printPermutation("ABC","ABA")
               ---> (str.length() == stringToPrint.length()); //ends
//etc

Remember that when you do this

    for (int i = 0; i < str.length(); i++) {
        printPermutation(str, stringToPrint + str.charAt(i));
    }

It firsts call recursion and then do nothing until method ends, therefore it "stays open" and wait, does not increment anything.

Upvotes: 1

wvdz
wvdz

Reputation: 16641

When you do stringToPrint + str.charAt(i), it creates a new String, and does not modify the value of stringToPrint. Of course, within the method call, the value of a new stringToPrint is different, but this is in a different scope.

Upvotes: 1

Related Questions