将嵌套循环转换为递归

Question

我使用了 3 个嵌套循环。现在我想将这些循环转换为递归。还有将循环转换为递归的通用方法吗？

#include <stdio.h>

#define f(x, y, z) ((x + y) * (y + z))

int main()
{
    int test_case, p, q, r, i, j, k, a[100001], b[100001], c[100001], sum;
    scanf("%d", &test_case);
    while (test_case--) {
        scanf("%d%d%d", &p, &q, &r);
        sum = 0;
        for (i = 0; i < p; i++) {
            scanf("%d", &a[i]);
        }
        for (i = 0; i < q; i++) {
            scanf("%d", &b[i]);
        }
        for (i = 0; i < p; i++) {
            scanf("%d", &c[i]);
        }
        for (i = 0; i < q; i++) { // I have convert this to recursion.
            for (j = 0; j < p; j++) {
                for (k = 0; k < r; k++) {
                    if (b[i] >= a[j] && b[i] >= c[k]) {
                        sum += f(a[j], b[i], c[k]);
                    }
                }
            }
        }
        printf("%d\n", sum % 1000000007);
    }
    return 0;
}

Answer 1

循环如下:

for (int i=0; i<n; i++) {
    func(i);
}

可以翻译为递归:

void rec_fun(int i,int n) {
    if (!(i<n)) return;
    func(i);
    rec_fun(i+1,n);
}
...
rec_fun(0,n);

所以:

for (i = 0; i < q; i++) { // I have convert this to recursion.
    for (j = 0; j < p; j++) {
        for (k = 0; k < r; k++) {
            if (b[i] >= a[j] && b[i] >= c[k]) {
                sum += f(a[j], b[i], c[k]);
            }
        }
    }
}

可以翻译为:

void rec_k(int k,int r,int i,int j) { // k-loop
    if (!(k<r)) return;
    if (b[i] >= a[j] && b[i] >= c[k]) {
        sum += f(a[j], b[i], c[k]);
    }
    rec_k(k+1,r,i,j); // recurse
}

void rec_j(int j,int p,int i,int r) { // j-loop
    if (!(j<p)) return;
    rec_k(0,r,i,j); // inner loop
    rec_j(j+1,p,i,r); // recurse
}

void rec_i(int i,int q,int p,int r) { // i-loop
    if (!(i<q)) return;
    rec_j(0,p,i,r); // inner loop
    rec_i(i+1,q,p,r); // recurse
}
...
rec_i(0,q,p,r);

我不确定这是否更具可读性或有用，但它满足您最初的需求。