如何将双层for循环转换为无重复输出的递归实现？

问题背景 #

原双层循环代码如下，需要转换为递归实现：

for(int i = 0; i <= MAX; ++i) {
    for(int j = 0; j + i <= MAX; ++j) {
        // print i, j
    }
}

当MAX=2时，预期输出为：

0, 0
0, 1
0, 2
1, 0
1, 1
2, 0

尝试的递归代码存在重复输出问题（比如1,1会被打印两次）：

void g(int i, int j) {
    if (i+j > maxint) {
        return;
    }
    // print i, j
    g(i, j+1);
    g(i+1, j);
}

问题原因 #

原递归的分支逻辑会导致同一个(i,j)被多条路径访问：比如g(0,1)会递归到g(1,1)，而g(1,0)也会递归到g(1,1)，因此重复输出。

修复后的递归代码 #

不使用记忆化的前提下，通过限制递归分支的触发条件，保证每个(i,j)只被访问一次：

#include <stdio.h>

#define MAX 2

void g(int i, int j) {
    if (i + j > MAX) {
        return;
    }
    // 打印当前i,j
    printf("%d, %d\n", i, j);
    // 先遍历当前i对应的所有j（j递增）
    g(i, j + 1);
    // 仅当j为初始值0时，才进入下一个i的遍历，避免重复路径
    if (j == 0) {
        g(i + 1, j);
    }
}

int main() {
    g(0, 0);
    return 0;
}

逻辑说明 #

• 递归优先沿着j+1的方向遍历，完成当前i对应的所有合法j值的打印，完全模拟原内层循环的行为。
• 只有当j=0时（即当前i的遍历起点），才触发i+1的递归分支，进入下一个i的遍历，这对应原外层循环的i++逻辑。
• 这种分支限制确保了每个(i,j)只会被一条路径访问，不会产生重复输出。

内容的提问来源于stack exchange，提问作者Nibor