Nested Loop Recursion

Question

I am learning recursions and I wanna to rewrite the following code with some "n" number of nested loops in terms of recursion

for (int a = 0; a < N; a++) {      //first loop
        for (int b = a + 1; b < N; b++) {       //second loop
            for (int c = b + 1; c < N; c++) {       // and for example n-th loop
                str = " ( " + Integer.toString(a)
                        + " , " + Integer.toString(b)
                        + " , " + Integer.toString(c) +" ) ";
                stringList.add(str);
            }
        }
    }

And when I call the

System.out.println(stringList);

The output should be as following

[ ( 0 , 1 , 2 ) ,  ( 0 , 1 , 3 ) ,  ( 0 , 2 , 3 ) ,  ( 1 , 2 , 3 ) ]

for N = 4 and 3 nested loops or

[ ( 0 , 1 , 2 ) ,  ( 0 , 1 , 3 ) ,  ( 0 , 1 , 4 ) ,  ( 0 , 2 , 3 ) ,  ( 0 , 2 , 4 ) ,  ( 0 , 3 , 4 ) ,  ( 1 , 2 , 3 ) ,  ( 1 , 2 , 4 ) ,  ( 1 , 3 , 4 ) ,  ( 2 , 3 , 4 ) ]

for N = 5 and 3 nested loops

I have tried to write whis code

 public static void recursionLoop(int i, int N, int M){  //M is the number of loops 
                                //N is the highest number the programm should reach
          List<Integer> list = new ArrayList<>();
            for (int a = i; a < N - 1; a++) {
                if (M > 0) {
                    smartIter(i + 1, N, M - 1);
                    list.add(a);

                }
            }

I cannot figure out how to reproduce my code to control the number of loops and the "N" number using recursion

Can you help me please, I am really want to undestand the way it should be written and logics of recursion

Thomas · Accepted Answer · 2016-09-15 15:46:19Z

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 it x
the maximum value N
an initial value (0, a + 1), let's call it start

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<>() );

I found your help very useful, thanks for that, but what about saving Integers to some datastructure I looked at your solution but didn't really get how to extract the numbers out. I mean, when passin the recursion through a loop, the integerof a previous loop, that I need to save to an array, is unaccessable to the next loop. So, is it really possible to do that?
@JohnWalker I expanded my answer since I also forgot the recursion depth you mentioned. I also must admit that handling the lists is simpler in my imagination that it probably is for a learner so I added an explanation for that as well - and I hope it is understandable.

mroman · Accepted Answer · 2016-09-15 16:25:35Z

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 :).

Thanks for help, I really appreciate that, but in your solution you are considering only two loops, what if I need to reproduce some N loops, and print out some M values?
It doesn't matter how many loops you have nested... the method is the same. I have updated my answer a little bit.
Ah now I get what you actually want. Sorry, I misunderstood that :(.

Collectives™ on Stack Overflow

Nested Loop Recursion

2 Answers 2

2 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related