如何将嵌套 for 循环更改为任意数量循环的递归函数？

Question

我找到了所有的组合，_nC _r :

#include <stdio.h>

void make_combination( int n, int r ){
    for (int x=1; x<n-r+1+1; x++){ 
        // because it is start from 1, add 1 to range, too
        for (int y=x+1; y<n-r+y+1; y++){
            for (int z=y+1; z<n-r+z+1; z++){
                printf("%d %d %d\n",x,y,z);            
            }
        }
    }
}

int main(void){
    int n, r;

    printf("Insert n : ");
    scanf("%d", &n);

    printf("Insert r : ");
    scanf("%d", &r);

    make_combination(n, r);
    return 0;
}

我想把它变成递归函数， 使其适用于变量 'r' 值， 因为我不想要 fixed 数量的 for 循环。

我试过了，但是不能做递归函数。

Answer 1

我们确实可以使用递归来构建 n 层的嵌套 for 层深层结构循环，在递归的最深层执行操作。

或者，等效地，我们可以构建 n-1 级别并显式执行最后一个 for 循环，像这样：

#include <stdio.h>

void rec(const char *pre, int n, int lo, int hi) {
    if (n == 0) return;
    if (n > 1) {
        for (int k = lo; k <= hi; k++) {
            char tmp[100]; // 100 is enough for home use
            sprintf(tmp, "%s %d", pre, k);
            rec(tmp, n - 1, k + 1, hi);
        }
    } else {
        for (int k = lo; k <= hi; k++) printf("%s %d\n", pre, k);
    }
}

int main(void) {
    rec("", 3, 0, 5); // use 3 values from 0 to 5
    return 0;
}

---

这会在 0..5 范围内创建经过排序的三元组数字。输出

 0 1 2
 0 1 3
 0 1 4
 0 1 5
 0 2 3
 0 2 4
 0 2 5
 0 3 4
 0 3 5
 0 4 5
 1 2 3
 1 2 4
 1 2 5
 1 3 4
 1 3 5
 1 4 5
 2 3 4
 2 3 5
 2 4 5
 3 4 5

---

将 main 中的调用替换为 rec("", 4, 0, 5); 会创建 4 元组；输出是

 0 1 2 3
 0 1 2 4
 0 1 2 5
 0 1 3 4
 0 1 3 5
 0 1 4 5
 0 2 3 4
 0 2 3 5
 0 2 4 5
 0 3 4 5
 1 2 3 4
 1 2 3 5
 1 2 4 5
 1 3 4 5
 2 3 4 5

---

添加了我写递归函数的思路

我知道递归解决方案基于“降低复杂性和递归”。所以当我知道如何做 n-1 循环时，我想“解决”n 循环。
但我不知道如何 n - 1 循环！

等等...我知道如何 0 循环。这很简单（但没有帮助）：什么都不做

if (n == 0) return;

我也知道如何做 1 循环。只需打印数字

if (n == 1) for (int k = lo; k <= hi; k++) printf("%d ", k);

这很好。可用于执行 n 循环。

如何进行 n 循环？
对于每个可用的数字，保存数字并使用 1 减少循环和调整限制进行递归。

正是它生成了该代码。编写代码后，我本可以专心研究它并简化某些方面，但我决定 post 原样。