This answer makes the assumption that the letters in the string are unique. Modifications would be required to prevent repeated anagrams otherwise.
One way to write an anagram function is to loop over each character c, recursively calculating the anagrams for the other letters, and appending the sub-anagrams to each c. The base case is when the string is only one character.
For example, here's a Java implementation:
import java.util.ArrayList;
import java.util.List;
public class Anagrams {
public static List<String> anagrams(String s) {
List<String> output = new ArrayList<String>();
if (s.length() == 0)
return output;
if (s.length() == 1) {
output.add(s);
return output;
}
for (int i = 0; i < s.length(); ++i) {
String c = s.substring(i, i + 1);
// Remove char c from string s to form string s2
String s2 = s.substring(0, i) + s.substring(i + 1);
// Calculate anagrams of s2 and append each to char c
List<String> anagrams2 = anagrams(s2);
for (String anagram : anagrams2) {
output.add(c + anagram);
}
}
return output;
}
public static void main(String[] args) {
List<String> l = anagrams("abc");
for (String s : l) {
System.out.println(s); // abc, acb, bac, bca, cab, cba
}
}
}
However, as is, that approach doesn't satisfy the constraint to not use any loops. The solution can be adapted to replace the for loops with functions that recursively increment an index, with the base case being when the index goes out-of-bounds.
For example, here's a Java implementation, followed by details on converting for loops to corresponding recursive functions.
import java.util.ArrayList;
import java.util.List;
public class Anagrams {
public static List<String> anagrams(String s) {
List<String> output = new ArrayList<String>();
if (s.length() == 0)
return output;
if (s.length() == 1) {
output.add(s);
return output;
}
// Recursively iterate over characters
class CharIter {
public void run(int char_idx) {
if (char_idx >= s.length())
return;
String c = s.substring(char_idx, char_idx + 1);
// Remove char c from string s to form string s2
String s2 = s.substring(0, char_idx) + s.substring(char_idx + 1);
// Calculate anagrams of s2 and append each to char c
List<String> anagrams2 = anagrams(s2);
// Recursively iterate over sub-anagrams
class AnagramIter {
public void run(int anagram_idx) {
if (anagram_idx >= anagrams2.size())
return;
output.add(c + anagrams2.get(anagram_idx));
run(anagram_idx + 1);
}
}
new AnagramIter().run(0);
run(char_idx + 1);
}
}
new CharIter().run(0);
return output;
}
public static void main(String[] args) {
List<String> l = anagrams("abc");
for (String s : l) {
System.out.println(s); // abc, acb, bac, bca, cab, cba
}
}
}
Converting Loops to Recursive Functions
For each converted loop, the condition for ending the loop was used as the base case of the recursive function, and the body of the loop was used as the body of the recursive function. To convey the idea, the example below shows how both a for loop and a recursive function can be used to print the integers between 0 and 3.
public class Loop {
private static int NUM_LOOPS = 4;
// Iterative looping
private static void loop_iter() {
for (int i = 0; i < NUM_LOOPS; ++i) {
System.out.println(i);
}
}
// Recursive looping
private static void loop_rec(int i) {
if (i >= NUM_LOOPS)
return;
System.out.println(i);
loop_rec(i + 1);
}
public static void main(String[] args) {
loop_iter(); // Outputs 0, 1, 2, 3
System.out.println();
loop_rec(0); // Outputs 0, 1, 2, 3
}
}
Because function calls require additional stack memory, the recursive approach would use more stack memory than the iterative approach. Some languages (e.g., Scheme) utilize tail call optimization so that recursive tail calls do not use any additional stack space, but this is not the case for Java.
