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.

Actually you should break the function down first:

A loop has a few parts:

1. the header, and processing before the loop. May declare some new variables

2. the condition, when to stop the loop.

3. the actual loop body. It changes some of the header's variables and/or the parameters passed in.

4. 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;
        }
    }
}

Like so:

public class Recursive {
    public void r(int i) {
        if (i < 1024) {
            i *= 2;
            System.out.println("Count is: " + i);
            r(i);
        }
    }

    public static void main(String[] args) {
        Recursive r = new Recursive();
        r.r(1);
    }
}

Googling "how to convert for loop to recursion," there's a similar answer here, and an article with an example here.

This is a pretty big hint but the basic idea is that your arguments store the current loop state.

for (int i = 1; i <= n; i++)
{
    // ....
}

is equivalent to:

private static void PerformAction(int n)
    {
        if (n > 0)
        {
            // Do something
            PerformAction(n - 1);
        }
    }

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

Your problem is not in the part you posted.

I added dummy implementations for all the classes and methods used in your method, and it runs quite fine, stopping at level 6.

package de.fencing_game.paul.examples;

import java.util.*;

public class RecursionAndLoop {


    private static class Move {
        private String id;
        public Move(String type) {
            this.id = type;
        }
        public String toString(){
            return "Move(" + id + ")";
        }

    }


    private static class GameState {
        private static int nextID;

        private int id;

        GameState() {
            this.id = nextID++;
        }

        public GameState getNewInstance(Move move) {
            return new GameState();
        }

        public int getPossibleMoveCount(int index) {
            return 5;
        }

        public Vector<Move> getPossibleMoves(int index) {
            Vector<Move> v = new Vector<Move>();
            for(int i = 0; i < 5; i++) {
                v.add(new Move(index + "×" + i));
            }
            return v;
        }

        public int getMarkCount(int index) {
            return 20 + index;
        }

        public String toString() {
            return "GameState[" + id + "]";
        }
    }

    private static class Node {
        private GameState state;
        private Move move;

        private List<Node> children;
        private Node parent;
        private int score;

        public Node(GameState s, Move m) {
            this.children = new ArrayList<Node>();
            this.state = s;
            this.move = m;
        }

        public void addChild(Node child) {
            children.add(child);
        }

        public void setParent(Node node) {
            parent = node;
        }

        public void setScore(int neu) {
            this.score = neu;
        }

        public int getDepth() {
            if(parent == null) {
                return 0;
            }
            return 1 + parent.getDepth();
        }

        /**
         * prints a simple tree view of this ZipNode and its descendants
         * on {@link System.out}.
         * @param prefix a prefix string to add before all lines.
         * @param self a prefix string to add before the line of this node
         *    itself (after the general prefix).
         * @param sub a prefix string to add before the line of all subnodes
         *    of this node (after the general prefix).
         */
        private void printTree(String prefix,
                               String self,
                               String sub) {
            System.out.println(prefix + self + state + " - " + move +
                               " - " + score);
            String subPrefix = prefix + sub;
            // the prefix strings for the next level.
            String nextSelf = " ├─ ";
            String nextSub =  " │ ";
            Iterator<Node> iterator =
                this.children.iterator();
            while(iterator.hasNext()) {
                Node child = iterator.next();
                if(!iterator.hasNext() ) {
                    // last item, without the "|"
                    nextSelf = " └─ ";
                    nextSub =  "   ";
                }
                child.printTree(subPrefix, nextSelf, nextSub);
            }
        }



    }


    int switchIndex(int index) {
        return index + 1;
    }



    private void makeTree(GameState prevState, Vector<Move> moves, Node parentNode, int index, int depthLimit) {

        if(prevState.getPossibleMoveCount(index) != 0){

            for(int i = 0; i < moves.size(); i++){

                Move thisMove = moves.get(i);
                GameState newState = prevState.getNewInstance(thisMove);
                Node child = new Node(newState, thisMove);
                parentNode.addChild(child);
                child.setParent(parentNode);

                if((child.getDepth() + 1) < depthLimit){

                    int newIndex = switchIndex(index);
                    Vector<Move> newMoves = newState.getPossibleMoves(newIndex);
                    makeTree(newState, newMoves, child, newIndex, depthLimit);

                }else{

                    child.setScore(newState.getMarkCount(index));
                }
            }
        }
    }


    public static void main(String[] params) {
        GameState start = new GameState();
        Vector<Move> m = new Vector<Move>();
        m.add(new Move("start"));
        Node root = new Node(start, null);
        int index = 7;
        int depthLimit = 6;
        new RecursionAndLoop().makeTree(start, m, root, index, depthLimit);
        root.printTree("", " ", "");
    }

}

(I changed a bit to generic types to avoid compiler warnings.)

Here is the output for depthLimit=4:

GameState[0] - null - 0
└─ GameState[1] - Move(start) - 0
   ├─ GameState[2] - Move(8×0) - 0
   │  ├─ GameState[3] - Move(9×0) - 29
   │  ├─ GameState[4] - Move(9×1) - 29
   │  ├─ GameState[5] - Move(9×2) - 29
   │  ├─ GameState[6] - Move(9×3) - 29
   │  └─ GameState[7] - Move(9×4) - 29
   ├─ GameState[8] - Move(8×1) - 0
   │  ├─ GameState[9] - Move(9×0) - 29
   │  ├─ GameState[10] - Move(9×1) - 29
   │  ├─ GameState[11] - Move(9×2) - 29
   │  ├─ GameState[12] - Move(9×3) - 29
   │  └─ GameState[13] - Move(9×4) - 29
   ├─ GameState[14] - Move(8×2) - 0
   │  ├─ GameState[15] - Move(9×0) - 29
   │  ├─ GameState[16] - Move(9×1) - 29
   │  ├─ GameState[17] - Move(9×2) - 29
   │  ├─ GameState[18] - Move(9×3) - 29
   │  └─ GameState[19] - Move(9×4) - 29
   ├─ GameState[20] - Move(8×3) - 0
   │  ├─ GameState[21] - Move(9×0) - 29
   │  ├─ GameState[22] - Move(9×1) - 29
   │  ├─ GameState[23] - Move(9×2) - 29
   │  ├─ GameState[24] - Move(9×3) - 29
   │  └─ GameState[25] - Move(9×4) - 29
   └─ GameState[26] - Move(8×4) - 0
      ├─ GameState[27] - Move(9×0) - 29
      ├─ GameState[28] - Move(9×1) - 29
      ├─ GameState[29] - Move(9×2) - 29
      ├─ GameState[30] - Move(9×3) - 29
      └─ GameState[31] - Move(9×4) - 29