Actually you should break the function down first:
A loop has a few parts:
the header, and processing before the loop. May declare some new variables
the condition, when to stop the loop.
the actual loop body. It changes some of the header's variables and/or the parameters passed in.
the tail; what happens after the loop and return result.
Or to write it out:
foo_iterative(params){
header
while(condition){
loop_body
}
return tail
}
Using these blocks to make a recursive call is pretty straightforward:
foo_recursive(params){
header
return foo_recursion(params, header_vars)
}
foo_recursion(params, header_vars){
if(!condition){
return tail
}
loop_body
return foo_recursion(params, modified_header_vars)
}
Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.
Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.
We can use a switch to work around that:
bar_recurse(params){
if(baseCase){
finalize
return
}
body1
bar_recurse(mod_params)
body2
bar_recurse(mod_params)
body3
}
bar_iterative(params){
stack.push({init, params})
while(!stack.empty){
stackFrame = stack.pop()
switch(stackFrame.resumPoint){
case init:
if(baseCase){
finalize
break;
}
body1
stack.push({resum1, params, variables})
stack.push({init, modified_params})
break;
case resum1:
body2
stack.push({resum2, params, variables})
stack.push({init, modified_params})
break;
case resum2:
body3
break;
}
}
}
Actually you should break the function down first:
A loop has a few parts:
the header, and processing before the loop. May declare some new variables
the condition, when to stop the loop.
the actual loop body. It changes some of the header's variables and/or the parameters passed in.
the tail; what happens after the loop and return result.
Or to write it out:
foo_iterative(params){
header
while(condition){
loop_body
}
return tail
}
Using these blocks to make a recursive call is pretty straightforward:
foo_recursive(params){
header
return foo_recursion(params, header_vars)
}
foo_recursion(params, header_vars){
if(!condition){
return tail
}
loop_body
return foo_recursion(params, modified_header_vars)
}
Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.
Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.
We can use a switch to work around that:
bar_recurse(params){
if(baseCase){
finalize
return
}
body1
bar_recurse(mod_params)
body2
bar_recurse(mod_params)
body3
}
bar_iterative(params){
stack.push({init, params})
while(!stack.empty){
stackFrame = stack.pop()
switch(stackFrame.resumPoint){
case init:
if(baseCase){
finalize
break;
}
body1
stack.push({resum1, params, variables})
stack.push({init, modified_params})
break;
case resum1:
body2
stack.push({resum2, params, variables})
stack.push({init, modified_params})
break;
case resum2:
body3
break;
}
}
}
Following up on @ratchet freak's answer, I created this example of how the Fibonacci function can be rewritten to a while loop in Java. Note that There's a much simpler (and efficient) way to rewrite the Fibonacci with a while loop though.
class CallContext { //this class is similar to the stack frame
Object[] args;
List<Object> vars = new LinkedList<>();
int resumePoint = 0;
public CallContext(Object[] args) {
this.args = args;
}
}
static int fibonacci(int fibNumber) {
Deque<CallContext> callStack = new LinkedList<>();
callStack.add(new CallContext(new Object[]{fibNumber}));
Object lastReturn = null; //value of last object returned (when stack frame was dropped)
while (!callStack.isEmpty()) {
CallContext callContext = callStack.peekLast();
Object[] args = callContext.args;
//actual logic starts here
int arg = (int) args[0];
if (arg == 0 || arg == 1) {
lastReturn = arg;
callStack.removeLast();
} else {
switch (callContext.resumePoint) {
case 0: //calculate fib(n-1)
callStack.add(new CallContext(new Object[]{arg - 1}));
callContext.resumePoint++;
break;
case 1: //calculate fib(n-2)
callContext.vars.add(lastReturn); //fib1
callStack.add(new CallContext(new Object[]{arg - 2}));
callContext.resumePoint++;
break;
case 2: // fib(n-1) + fib(n-2)
callContext.vars.add(lastReturn); //fib2
lastReturn = (int) callContext.vars.get(0) + (int) callContext.vars.get(1);
callStack.removeLast();
break;
}
}
}
return (int) lastReturn;
}
Videos
Have a look at your loops, i.e. how they are related to each other. As an example let's take the 1st and 2nd:
for (int a = 0; a < N; a++) {
for (int b = a + 1; b < N; b++) {
As you can see each loop uses 3 values/variables:
- the loop variable (
a,b), let's call itx - the maximum value
N - an initial value (
0,a + 1), let's call itstart
Thus both loops could be rewritten as
for (int x = start; x < N; x++ ) { ... }
Now put that into a method and add a condition for the recursion:
void runInnerLoop( int start, int N) {
for (int x = start; x < N; x++ ) {
runInnerLoop( x + 1, N );
}
}
Note that in your case you'd need to also pass the list of strings as a parameter and add a string to it, either before of after the recursion.
Also note that I didn't include any additional check whether to do the recursive call or not. That way you'd eventually end up with start == N but the loop condition would take take of that. Adding a condition like if( x < N - 1 ) would prevent an unnecessary recursive call at the cost of additional condition evaluation. Which option would be faster remains to be seen but since that's probably not really relevant I'd opt for the easier to read version.
However, since you're current learing recursion: keep in mind to always check whether the abort condition can be reached in all cases or not. Otherwise you'd run into StackOverflowError etc. - which could also happen if your N is too big in which case you'd need a different approach.
Edit:
I must admit that I overlooked a piece of information in your question, i.e. there is a limited recursion depth which you called M. Thus I'll expand my answer with that information and I'll also explain how to get the "lists" you want to print.
Basically handling the recursion depth is easy: you pass the current depth + 1 to each call as well as the maximum depth and before doing a recursive call you check for depth < maxDepth - if this is true you do a recursice call, if it is false you print the current branch (i.e. the "list" of integers).
Handling the lists isn't that hard but doing it efficiently requires some thought. Basically each iteration adds a new list, i.e. 0,1,2 and 0,2,3 are different lists.
If you'd use lists you'd have to pass the current list to the recursive call and inside the loop create a new list, add all the values of the top list to it and finally add the current loop variable to it (e.g. List<Integer> list = new ArrayList<>( topList ); list.add(x);).
However, you only need the lists in the deepst calls, i.e. when printing or collecting them. This means all those intermediate lists are a waste of time and memory. So instead you might want to use a Stack to track the current loop values, i.e. at the start of an iteration you push the current value to the stack and remove the top value at the end of the iteration. That way you can reuse the same stack and print only the current loop variables (or collect them into a new list for later use).
Here's the top example using recursion depth and a stack:
void runInnerLoop( int start, int N, int depth, int maxDepth, Stack<Integer> stack) {
for (int x = start; x < N; x++ ) {
stack.push( x ); //add the current value to the stack
if( depth < maxDepth ) { //max depth not reached, do another recursion
runInnerLoop( x + 1, N, depth + 1, maxDepth, stack );
} else {
System.out.println( stack ); //max depth reached, print now
}
stack.pop(); //remove the top value from the stack
}
}
The inital call for your first example (N=4, maxDepth=3) would look like this:
runInnerLoop( 0, 4, 1, 3, new Stack<>() );
Update 4
static List<List<Integer>> f(int init, int N, int depth, List<Integer> ls) {
List<List<Integer>> all = new ArrayList<>();
for(int i = init; i < N; i++) {
List<Integer> ls_ = new ArrayList<Integer>();
ls_.addAll(ls);
ls_.add(i);
if(depth == 0) {
all.add(ls_);
} else {
all.addAll(f(i + 1, N, depth-1, ls_));
}
}
return all;
}
Original
Without spoiling too much maybe this helps you:
for (int i = 0; i < 10; i++)
System.out.println(i);
is semantically the same as:
public static void f(final int i) {
if (i < 10) {
System.out.println(i);
For.f(i + 1);
}
}
You will also notice that:
while(i < 10) {
System.out.println(i);
i++;
}
is basically the same thing and can be translated to recursion the same way.
I wouldn't recommend coding like this but you can rewrite every for-loop to a recursive function this way. for loops don't consume as much stack space.
When you nest for loops you can translate them using the same algorithm:
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++)
System.out.println(x + "," + y);
becomes two functions f,g:
public static void f(final int x) {
if (x < 3) {
For.g(x, 0);
For.f(x + 1);
}
}
public static void g(final int x, final int y) {
if (y < 3) {
System.out.println(x + "," + y);
For.g(x, y + 1);
}
}
Update
To answer the comments:
It doesn't matter how many for-loops you have nested. Every for-loop can be rewritten as a recursive function. If you have N nested for-loops you can rewrite them to N recursive functions. The method is as follow:
If you have for(TYPE i = INIT; CONDITION; P-EXPRESSION) { CODE } you can translate it to:
function NAME(TYPE i) {
if(CONDITION) {
CODE
P-EXPRESSION
NAME(i); //this is the recursive call
}
}
NAME(INIT)
If you have nested for-loops the method is the same but you have to pass local variables as parameters.
for(int a = INIT_A; CONDITION_A; P-EXPRESSION_A) {
CODE_A
for(int b = INIT_B; CONDITION_B; P-EXPRESSION_B) {
CODE_B
//^- if you use a in this you have to pass a as a parameter
for(int c = INIT_C; CONDITION_C; P-EXPRESSION_C) {
CODE_C
//^- same deal
}
}
}
Becomes roughly (pseudo-code):
function f(int a) {
if(CONDITION_A) {
CODE_A
g(a, INIT_B);
P-EXPRESSION_A
f(a);
}
}
function g(int a, int b) {
if(CONDITION_B) {
CODE_B
h(a,b, INIT_C);
P-EXPRESSION_B
g(a, b);
}
}
function h(int a, int b, int c) {
if(CONDITION_C) {
CODE_C
P-EXPRESSION_C
h(a,b,c);
}
}
f(INIT_A)
Update 2
The direct 1:1 translation using the above method gives you:
public static List<String> f(int a, int N, List<String> stringList) {
if(a < N) {
g(a, a + 1, N, stringList);
f(a + 1, N, stringList);
}
return stringList;
}
public static List<String> g(int a, int b, int N, List<String> stringList) {
if(b < N) {
h(a, b, b+1, N, stringList);
g(a, b+1, N, stringList);
}
return stringList;
}
public static List<String> h(int a, int b, int c, int N, List<String> stringList) {
if(c < N) {
String str = " ( " + Integer.toString(a)
+ " , " + Integer.toString(b)
+ " , " + Integer.toString(c) +" ) ";
stringList.add(str);
h(a, b, c+1, N, stringList);
}
return stringList;
}
It's not beautiful/optimal code but it's a translation of each for-loop to a recursive function.
Update 3
A nicer translation would have the form:
h a b c n
|c < n = (a,b,c) : h a b (succ c) n
|otherwise = []
g a b n
|b < n = h a b (succ b) n ++ g a (succ b) n
|otherwise = []
f a n
|a < n = g a (succ a) n ++ f (succ a) n
|otherwise = []
main = print $ f 0 4
but this would translate to java as:
public static List<String> f(int a, int N) {
if(a < N) {
List<String> ls = new ArrayList<String>();
ls.addAll(g(a, a + 1, N));
ls.addAll(f(a + 1, N));
return ls;
}
return new ArrayList<String>();
}
public static List<String> g(int a, int b, int N) {
if(b < N) {
List<String> ls = new ArrayList<String>();
ls.addAll(h(a,b,b+1,N));
ls.addAll(g(a,b+1,N));
return ls;
}
return new ArrayList<String>();
}
public static List<String> h(int a, int b, int c, int N) {
if(c < N) {
String str = " ( " + Integer.toString(a)
+ " , " + Integer.toString(b)
+ " , " + Integer.toString(c) +" ) ";
List<String> ls = new ArrayList<String>();
ls.add(str);
ls.addAll(h(a,b,c+1,N));
return ls;
}
return new ArrayList<String>();
}
Which is not efficient Java :).
Think of a for loop as a little anonymous function that takes the loop index value as a parameter. In order to start the next iteration of the loop, the function can return a call to itself with a new value for the loop index parameter.
Like this:
Object loop(int i, Object data) {
if (i > 0) {
return loop(i - 1, evolve(data));
} else {
return data;
}
}
That's the same as this:
for ( ; i > 0; i--) {
data = evolve(data);
}
In some languages, particularly Scheme, and who knows maybe Java 8 or 9, the compiler is guaranteed to compile a recursive function such as the function loop above just the same as it compiles the for loop above.
In other languages, including the current and past versions of Java, nearly all compilers will make an executable that builds a big call stack. When the call stack is large it may even overflow the permitted size and crash the program.
Haters aside, let's do this! [1]
Given:
int x = 3;
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
for (int k = 0; k < x; k++){
list.add(array[i] + array[j] + array[k]);
}
}
}
Let's consider that each loop is it's own recursive function - as this makes the recurrence cases much easier! This is also the only "non-thinking" method I know of to turn the loops into recursion. The recursive depth will be limited to 3*x => i+j+k so it's "fairly safe" for a smallish[2] x.
In Java it requires a separate method for each loop to encode this structure. (In a language with higher-order functions these three functions might be abstractly combined .. but not in Java [7].)
void loopI(int i) {
if (i < x) {
loopJ(0); // "start j loop"
loopI(i++); // "next i loop" / recurrence case
}
// "end loop" / base case
}
void loopJ(int j) {
if (j < x) {
loopK(0);
loopJ(j++);
}
}
void loopK(int k) {
if (k < x) {
list.add(array[i] + array[j] + array[k]);
loopK(k++);
}
}
// do it!
loopI(0);
All of these could be combined into a single recursive function, but that makes handling the recurrence cases a bit tougher as "thinking" and additional conditionals (or mod expressions, perhaps) are required to advance the state.
Here is an example of a combined recursive function (this is incorrect when x is 0). Unlike the three method approach above, the stack depth will grow to x^3 => i*j*k. This will easily kill Java's recursion limits - even for smallish values of x- as Java [7] doesn't have tail-call optimization.
void loop(int i, int j, int k) {
list.add(array[i] + array[j] + array[k]);
// advance states
k++;
if (k == x) { k = 0; j++; }
if (j == x) { j = 0; i++; }
if (i == x) { i = 0; }
// terminate on all wrap-around
if (i == 0 && j == 0 && k == 0) { return; }
// recurse
loop(i, j, k);
}
[1] YMMV, for theoretical purposes only - I love recursion, but it's not suited for this case in Java.
[2] For some value of "smallish". See how deep your stack can go!
A loop like:
for (int i=0; i<n; i++) {
func(i);
}
can be translated to recursion as:
void rec_fun(int i,int n) {
if (!(i<n)) return;
func(i);
rec_fun(i+1,n);
}
...
rec_fun(0,n);
So:
for (i = 0; i < q; i++) { // I have convert this to recursion.
for (j = 0; j < p; j++) {
for (k = 0; k < r; k++) {
if (b[i] >= a[j] && b[i] >= c[k]) {
sum += f(a[j], b[i], c[k]);
}
}
}
}
can be translated as:
void rec_k(int k,int r,int i,int j) { // k-loop
if (!(k<r)) return;
if (b[i] >= a[j] && b[i] >= c[k]) {
sum += f(a[j], b[i], c[k]);
}
rec_k(k+1,r,i,j); // recurse
}
void rec_j(int j,int p,int i,int r) { // j-loop
if (!(j<p)) return;
rec_k(0,r,i,j); // inner loop
rec_j(j+1,p,i,r); // recurse
}
void rec_i(int i,int q,int p,int r) { // i-loop
if (!(i<q)) return;
rec_j(0,p,i,r); // inner loop
rec_i(i+1,q,p,r); // recurse
}
...
rec_i(0,q,p,r);
I'm not sure this is either more readable or useful, but it meets your initial needs.
Let us assume that the intention of this code is to only calculate the sum.
You can make a function as
int recurse_sum(int i, int j, int k) {
int res = .... // Logic for calculating sum for these indices i, j, k.
k++;
if (k==r) {
k = 0;
j++;
}
if(j==p){
j=0;
i++;
}
if(i==q){
return res;
}
return res + recurse_sum(i,j,k);
}
Now you can just call with recurse_sum(0,0,0);
The rest of the parameters can either be made global or just passed along with i,j,k.
I hope this helps.
Edit:
As mentioned by @dlasalle this code can be made open to tail call recursion optimization by placing the call at the end of the function.
In that case you can have the following version.
int recurse_sum(int i, int j, int k, int sum) {
int res = .... // Logic for calculating sum for these indices i, j, k.
k++;
if (k==r) {
k = 0;
j++;
}
if(j==p){
j=0;
i++;
}
if(i==q){
return res + sum;
}
return recurse_sum(i,j,k,res+sum);
}
Here the function ends with returning the value from the inner call and hence can be easily optimized.
Ofcourse in this case it will have to be called as recurse_sum(0,0,0,0);
You have a list of House with position with either 0, 1, 2, 3, 4. Let me use a annotation of H{i} to represent a House with position i which 0 <= i <= 4.
If your input list is
[ H{0}, H{1}, H{2}, H{3}, H'{3}, H{4}, H'{4} ]
which H' is another house
the result is
[
[ H{0}, H{1}, H{2}, H{3}, H{4} ],
[ H{0}, H{1}, H{2}, H{3}, H'{4} ],
[ H{0}, H{1}, H{2}, H'{3}, H{4} ],
[ H{0}, H{1}, H{2}, H'{3}, H'{4} ],
]
This give me following information:
- When iterate to
H{3}, it find aHousewith next position, i.e. 4. - When iterate to
H{4}, it will create the 1st list and store the houses with a position of 0, 1, 2, 3 iterated previously. - After reach
H{4}, it will find anotherHousewith position 4, i.e.H'{4}, and create 2nd list and store the houses iterate previously exceptH{4}. - When reach the end of the list, it is back to
H'{3}and iterate the list again to create 3rd and 4th list.
From #2, we know that:
- We need to create a list to store the
Houseif house position = 4 - There should be a
bufferto store theHousewith position 0, 1, 2, 3, iterated before.buffer[0]will storeH{0},buffer[1]will storeH{2}, etc.
From #3, we know that:
If reach House with position 4, the list will further iterate until reach the end of the list.
We can have a base function as follows:
public static List<House[]> foo(House[] houses, List<House> buffer) {
List<House[]> list = new ArrayList<House[]>();
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
if (house.getPosition() == 4) {
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
}
}
}
return list;
}
What the above do?
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
At the very beginning, buffer is empty with size = 0. If it find a House with position 0, it will be stored into the buffer and the buffer size becomes 1. When the list iterate to next House with position = 1 (the buffer size), it will be stored. Otherwise, find another House that match the condition.
if (house.getPosition() == 4) {
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
}
As mentioned, a list will be created to store the House in the buffer if there is a House with position 4. buffer.remove(buffer.size() - 1) is to remove the last House with position 4 such that another House can be stored into buffer.
So far, no recursive call is in our function since the case for House with position 4 do not need it.
Let's look back to #1 and #4. We know that:
If reach a House with position other than 4, it find a House with next position and create a list when iterate to House with position 4.
It means that our base function will be called if a House with position other than 4. So, we can modify our function as follows:
public static List<House[]> foo(House[] houses, List<House> buffer) {
List<House[]> list = new ArrayList<House[]>();
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
if (house.getPosition() == 4) { // base case, no recursive call
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
} else { // recursive case
list.addAll(foo(houses, buffer));
}
}
}
if (buffer.size() > 0) {
buffer.remove(buffer.size() - 1);
}
return list;
}
In summary, we have 2 case for the problem. One is the base case to handle House with position 4 and another case is to handle House with position other than 4 which need a recursive call.
Recursive function normally divide problem into cases. The function calls itself recursively on a smaller list of Houses until reaching the base case. Hope this can help.
Since @Wilson asked how I'd do it, here's a way that will work for any assortment of position values in the input, even if they're not contiguous. Call with something like:
List<House[]> houseTupleList = new HouseTupleListBuilder()
.addAll(houses)
.build();
The output tuples will contain values for the populated positions in ascending order.
Note that if a position number is missing entirely in the input (e.g. in the example there were only houses with positions 0,1,3,4), this code will happily produce tuples using only the present values (e.g. in my example, they would be 4-tuples). If you don't want that, you should call the builder's method expectPosition(i) for all expected positions i. Then if the input is lacking any position, the output will be empty, just as the OP's version.
class HouseTupleListBuilder {
private final NavigableMap<Integer, List<House>> housesByPosition = new TreeMap<>();
HouseTupleListBuilder addAll(Collection<House> houses) {
for (House house : houses) {
expectPosition(house.getPosition());
housesByPosition.get(house.getPosition()).add(house);
}
return this;
}
HouseTupleListBuilder expectPosition(int i) {
housesByPosition.putIfAbsent(i, new ArrayList<>());
return this;
}
List<House[]> build() { return new TupleEnumerator().enumeration(); }
private class TupleEnumerator {
private final Map<Integer, House> houseByPosition = new TreeMap<>();
private final List<House[]> tuples = new ArrayList<>();
private void enumerateFor(NavigableSet<Integer> positions) {
if (positions.isEmpty()) {
tuples.add(houseByPosition.values().toArray(new House[0]));
return;
}
int first = positions.first();
for (House house : housesByPosition.get(first)) {
houseByPosition.put(first, house);
enumerateFor(positions.tailSet(first, false));
}
}
private List<House[]> enumeration() {
enumerateFor(housesByPosition.navigableKeySet());
return tuples;
}
}
}
Yes. This can be performed by recursive programming.
I assume you do not like to WRITE DOWN these nested for's in source code - as in your example, because this is really ugly programming - like the commentors explain.
The following (pseudo Java-like) code illustrates it. I assume a fixed depth for the nesting. Then you actually like to loop over an integer vector of dimension depth.
int[] length = new int[depth];
int[] counters = new int[depth];
The array counters has to be initialised to 0 (Arrays.fill(counters,0)). The array length has to be initialised to the number of iterations for the respective for loop.
I assume that you like to perform a certain operation within the inner loop. I will call this
performOperation(int[] counters);
- it depends on the multi-dimensional counter, i.e. the counters of the outer for's.
Then you can run the nested for loops by calling
nestedLoopOperation(counters, length, 0);
where
void nestedLoopOperation(int[] counters, int[] length, int level) {
if(level == counters.length) performOperation(counters);
else {
for (counters[level] = 0; counters[level] < length[level]; counters[level]++) {
nestedLoopOperation(counters, length, level + 1);
}
}
}
In your case your System.out.println() would be
performOperation(int[] counters) {
String counterAsString = "";
for (int level = 0; level < counters.length; level++) {
counterAsString = counterAsString + counters[level];
if (level < counters.length - 1) counterAsString = counterAsString + ",";
}
System.out.println(counterAsString);
}
I created this program to show all the different possible combination of cards (non repeating). It uses recursive for loops. Maybe it can help you.
//I'm lazy, so yeah, I made this import...
import static java.lang.System.out;
class ListCombinations {
//Array containing the values of the cards
static Symbol[] cardValues = Symbol.values();
//Array to represent the positions of the cards,
//they will hold different card values as the program executes
static Symbol[] positions = new Symbol[cardValues.length];
//A simple counter to show the number of combinations
static int counter = 1;
/*Names of cards to combine, add as many as you want, but be careful, we're
talking about factorials here, so 4 cards = 24 different combinations (4! = 24),
but 8 cards = 40320 combinations and 13 cards = 6.23 billion combinations!*/
enum Symbol {
AofSpades, TwoofSpades, ThreeofSpades, FourofSpades
}
public static void main(String args[]) {
//I send an argument of 0 because that is the first location which
//we want to add value to. Every recursive call will then add +1 to the argument.
combinations(0);
}
static void combinations(int locNumber) {
/* I use a recursive (repeating itself) method, since nesting for loops inside
* each other looks nasty and also requires one to know how many cards we will
* combine. I used 4 cards so we could nest 4 for loops one after another, but
* as I said, that's nasty programming. And if you add more cards, you would
* need to nest more for loops. Using a recursive method looks better, and gives
* you the freedom to combine as many cards as you want without changing code. */
//Recursive for loop nesting to iterate through all possible card combinations
for(int valueNumber = 0; valueNumber < cardValues.length; valueNumber++) {
positions[locNumber] = cardValues[valueNumber];
if (locNumber < (cardValues.length-1)) {
combinations(locNumber + 1);
}
//This if statement grabs and displays card combinations in which no card value
// is repeated in the current "positions" array. Since in a single deck,
// there are no repeated cards. It also appends the combination count at the end.
if (locNumber == (cardValues.length-1) && repeatedCards(positions)) {
for (int i = 0; i < cardValues.length; i++) {
out.print(positions[i]);
out.print(" ");
}
out.printf("%s", counter);
counter++;
out.println();
}
}
}
static boolean repeatedCards(Symbol[] cards) {
/*Method used to check if any cards are repeated in the current "positions" array*/
boolean booleanValue = true;
for(int i = 0; i < cardValues.length; i++) {
for(int j = 0; j < cardValues.length; j++) {
if(i != j && cards[i] == cards[j]) {
booleanValue = false;
}
}
}
return booleanValue;
}
}
I suggest you focus on other activities. Java already includes a function to do what you are implementing, and that is String.contains(CharSequence) like
if (str1.contains(str2)) { // <-- wherever you would have called "checkString"
// ...
}
public class Test {
public static void main(String[] args) {
System.out.println(isSubstring("ankur", "ku"));
}
public static boolean isSubstring(String str1, String str2) {
if ((str1 == null) || (str2 == null) || str1.isEmpty()) {
return false;
} else if (str1.startsWith(str2)) {
return true;
} else {
return isSubstring(str1.substring(1), str2);
}
}
}
Java for loops don't support looping over multi-dimensional structures.
This is a recursive method which will emulate n-nested for loops.
Note that params is a clone of starts, because otherwise the first calls to doCalculation() would be passed a mostly uninitialized array, in this case [4, 0, 0], where 4 is the first element in starts.
int[] starts = new int[]{4, 5, 6};
int[] limits = new int[]{7, 8, 10};
int[] incrementers = new int[]{1, 2, 3}; // elements cannot be <= 0
int[] params = starts.clone(); // must be a clone of starts
doCalculations(starts, limits, incrementers, params, 0);
void doCalculations(int[] starts, int[] limits, int[] incrementers, int[] params, int current) {
if(current == limits.length) {
return;
}
for(int i = starts[current]; i < limits[current]; i += incrementers[current]) {
params[current] = i;
if(current == params.length - 1) {
doCalculation(params);
}
doCalculations(starts, limits, incrementers, params, current + 1);
}
}
If the count of loops is not fixed, you should use a recursion. It can be called to any depth.
void calc(List<Integer> params, int loopsCount, int[] loopLimits)
int limit = loopLimits[loopsCount];
for (int i = 0; i < limit; i++) {
params.add(i);
if (loopsCount == 0) doCalculation(params)
else calc(params, loopsCount - 1, loopLimits);
params.removeLast();
}
}
Of course, you can make it in one for loop by having an array of limits limits, multiplying all of its members, and run a loop up to the final product. But then you will lose the information of each index, so you would need to compute it and store in an temporary array, such es
int product = limits[0] * limits[1] * ... * limits[n];
...
int[] indexes = new int[n];
for (i = 0; i < product; i++) {
doCalculation(indexes);
increaseIndex = 0;
while(true) {
if (indexes[increaseIndex]++ == limits[increaseIndex])
indexes[increaseIndex++] = 0;
else break;
}
}
but this is unlegible and unclear. However, maybe faster then recursion.
Assuming you have your list set up so that tab[0] is the list of the first strings to print, tab[1] the following strings, etc., you can use recursion as follows:
void print_rec(List<String>[] tab, int depth, String str) {
int maxdepth = tab.length - 1;
for (int i = 0; i < tab[depth].size(); i++) { // number of strings at this depth
if (depth == maxdepth) {
System.out.println(str + tab[depth].get(i)); // print line
// no more lists to go through, print the line
} else {
print_rec(tab, depth + 1, str + tab[depth].get(i) + " ");
// add next entry at this level to str and recurse
}
}
// done with this depth, go back up one
}
void printAll(List<Strings>[] tab) {
print_rec(tab, 0, "");
}
This covers all the entries exactly like nested loops.
Here is a solution. It's a modification of my answer to your other post: how to use recursion for nested 'for' loops.
public static void iterate(Object[] previousValues, List<Object>[] tabs) {
if (tabs.length == 0) {
System.out.println(Arrays.toString(previousValues));
}
else {
final Object[] values = new Object[previousValues.length + 1];
for (int i = 0; i < previousValues.length; i++) {
values[i] = previousValues[i];
}
final List<Object>[] nextTabs = new List[tabs.length - 1];
for (int i = 0; i < nextTabs.length; i++) {
nextTabs[i] = tabs[i + 1];
}
for (Object o : tabs[0]) {
values[values.length - 1] = o;
iterate(values, nextTabs);
}
}
}
public static void iterate(List<Object>[] tabs) {
iterate(new Object[0], tabs);
}
public static void main(String[] args) {
final List<String> firstTab = new ArrayList<>();
firstTab.add("England");
final List<String> secondTab = new ArrayList<>();
secondTab.add("London");
secondTab.add("Liverpool");
final List<String> thirdTab = new ArrayList<>();
thirdTab.add("DG300");
thirdTab.add("SS500");
iterate(new List[]{firstTab, secondTab, thirdTab});
}