C 编程 - 递归的两个 for 循环

Question

我试图制作可以模拟两个 for 循环的递归函数。因此，函数必须这样做：

int recursion(int n, int i, int j)
{
    for(i=0; i<n; i++)
    {
        for(j=i+1; j<n; j++)
        {
            printf("%d %d\n", i, j);
        }
    }
}

但是，我希望它是递归的。我试过类似的东西：

int recursion(int n, int i, int j)
{
    if(i<n)
    {
        if(j<n)
        {
            printf("%d %d\n", i, j);
            recursion(n, i+1, j+1);
        }
        recursion(n, i+1, i+1+1);
    }
}

我会在 main 中调用递归

recursion(10, 0, 1);

但是这两个版本的函数的输出不同。谁能告诉我我在哪里与递归错误？

Answer 1

For simulating nested for loops, you should only increment one of your counter variables for each recursive call, depending on whether you're "in" the inner or outer loop. Also, the outer loop calls need to reset the inner loop counter to zero.

/* i for outer loop, j for inner loop, both going 0 to n-1 */
void recursion(int n, int i, int j)
{
  if (i < n) {
    if (j < n) {
      // inner loop when j < n
      printf("i=%d, j=%d\n",i,j); // inner loop body
      recursion(n, i, j+1); // increment inner counter only!
    } else { // when j has reached n...
      // outer loop, which restarts inner loop
      recursion(n, i+1, 0); // increment outer counter, reset inner
                            // since we're starting a new inner loop
    }
  }
}

If called initially as recursion(N, 0, 0) this should be roughly equivalent to:

for (i = 0; i < N; i++) {
  for (j = 0; j < N; j++) {
    printf("i=%d, j=%d\n", i, j);
  }
}

...except that it doesn't account for modifications of i within the inner loop (none happen in these examples, but if the inner loop did set i larger than N, the recursive version would break both loops without finishing the inner loop first).