嵌套循环递归 [英] Nested Loop Recursion

问题描述

我正在学习递归，我想用递归方面的n"个嵌套循环重写以下代码

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

当我打电话给

System.out.println(stringList);

输出应该如下

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

对于 N = 4 和 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 ) ]

对于 N = 5 和 3 个嵌套循环

for N = 5 and 3 nested loops

我已经尝试过编写 whis 代码

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

                }
            }

我不知道如何重现我的代码以使用递归来控制循环数和N"数

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

推荐答案

看看你的循环，即它们是如何相互关联的.我们以第一个和第二个为例:

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++) {      

如您所见，每个循环使用 3 个值/变量:

As you can see each loop uses 3 values/variables:

• 循环变量(a, b)，我们称之为x
• 最大值N
• 一个初始值(0, a + 1)，我们称之为start

• 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.

另请注意，我没有包括任何额外的检查是否进行递归调用.这样你最终会得到 start == N 但循环条件会接受它.添加像 if( x < N - 1 ) 这样的条件可以防止不必要的递归调用，代价是额外的条件评估.哪个选项会更快还有待观察，但由于这可能不是真正相关，我会选择更易于阅读的版本.

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.

但是，由于您当前正在学习递归:请记住始终检查是否在所有情况下都可以达到中止条件.否则，您会遇到 StackOverflowError 等 - 如果您的 N 太大，这种情况也可能发生，在这种情况下，您需要不同的方法.

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.

我必须承认，我忽略了您问题中的一条信息，即您称之为 M 的有限递归深度.因此，我将使用该信息扩展我的答案，并且我还将解释如何获取您想要打印的列表".

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.

基本上处理递归深度很容易:您将当前深度 + 1 以及最大深度传递给每个调用，然后在进行递归调用之前检查 depth <maxDepth - 如果为真，则执行递归调用，如果为假，则打印当前分支(即整数列表").

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

处理列表并不难，但要有效地完成它需要一些思考.基本上每次迭代都会添加一个新列表，即 0,1,2 和 0,2,3 是不同的列表.

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.

如果您使用列表，则必须将当前列表传递给递归调用，并在循环内创建一个新列表，将顶部列表的所有值添加到它，最后将当前循环变量添加到它(例如 List list = new ArrayList<>( topList ); list.add(x);).

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

但是，您只需要最深调用中的列表，即在打印或收集它们时.这意味着所有这些中间列表都是浪费时间和内存.因此，您可能希望使用 Stack 来跟踪当前循环值，即在迭代开始时将当前值推送到堆栈并在迭代结束时删除顶部值.这样您就可以重用相同的堆栈并仅打印当前循环变量(或将它们收集到一个新列表中以备后用).

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
  }  
}

第一个示例(N=4，maxDepth=3)的初始调用如下所示:

The inital call for your first example (N=4, maxDepth=3) would look like this:

runInnerLoop( 0, 4, 1, 3, new Stack<>() );

这篇关于嵌套循环递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！