It is easy to write the code to nest the for-loop n-times if you know the value of n. For example, if you know n=3, then the code is as follows:
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
}
}
}
But what if the value of n is just a variable? How to write code for this? It can be solved using recursive function. The basic code is as follows:
public void func(int count, int n){
if( count == n){
return;
}
for(int i=0; i<length; i++){
func(count+1,n);
}
}
And you just need to call func(0,n); The basic idea here is to pass the count number as an argument to the next recursive call. And the next recursive call can determine if to finish or continue based on that value. Here we only pass the count number to the subsequent call. We can also pass other values in the arguments to the next recursive call and solve some quite complex problems! If we make some twists in the actual body of the function, this code can be even more powerful!
Permutation Problem
Problem: Print out all the permutations of some letters.
Inputs: An array of characters inChars of length n, where n is a positive integer
Outputs: All possible permutations of these characters.
Solution 1:
public void func(int count, boolean[] used, char[] chs, StringBuilder sb){
if ( count == used.length){
System.out.println(sb.toString());
}
for(int i=0; i<chs.length; i++){
if( !used[i]){
sb.append(chs[i]);
used[i] = true;
func(count+1, used, chs, sb);
used[i] = false;
sb.setLength(count);
}
}
}
public void solve(char[] inChars){
boolean[] used = new boolean[inChars.length];
StringBuilder sb = new StringBuilder();
func(0, used, inChars, sb);
}
Test Results:
For inChars = {'a','b','c'}, the output is
abc acb bac bca cab cba
Notes:
- The above code for permutation is a little different from the n-Queens problem. In the n-Queens problem, each subsequent loop still goes throug all the positions, whereas here, the subsequent loops only go through partial values. They use the used[] array to check if a value has already been used.
