Write a recursive method that has two parameters, first and second, that are both strings. The method should print all rearrangements of the letters in first followed by second. For example, if first is the string "CAT" and second is the string "MAN", then the method would print the strings CATMAN, CTAMAN, ACTMAN, ATCMAN, TACMAN, and TCAMAN. The stopping case of the method occurs when the length of first has zero characters. We’ll leave the recursive thinking up to you, but we should mention three string techniques that will make things go more smoothly.

These techniques are:

(1) The following expression is a string consisting of all of first followed by character number i from second:

first + second.charAt(i)

(2) The following expression is a string consisting of all of second with character i removed. The value of i must be less than the last index of the string. The first part of the expression is everything from location 0 to location i-1, and the second part of the expression is everything after location i.

second.substring(0, i)

+

second.substring(i+1);

(3) The following expression is a string consisting of all of second except the last character. For this to work, the string must be non-empty.

second.substring(0, s.length()-1)

The stopping case occurs when the length of the second string is zero (in which case you just print the first string). For the recursive case, make one recursive call for each character in the second string.

During each recursive call, you take one character out of second and add it to the end of first.