将嵌套循环转换为递归

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

我不知道这是无论是更具可读性还是有用的，但它满足您的初步需求：可以作为翻译。

Answer 2

让我们假设这个代码的意图是只计算总和。

，您可以拨打功能

int recurse_sum(int i, int j, int k) { 
     int res = .... // Logic for calculating sum for these indices i, j, k. 
     k++; 
     if (k==r) { 
      k = 0; 
      j++; 
     } 
     if(j==p){ 
      j=0; 
      i++; 
     } 
     if(i==q){ 
      return res; 
     } 
     return res + recurse_sum(i,j,k); 
} 

现在你可以只是recurse_sum(0,0,0); 参数的其余部分可以进行全球或只是I，J，K一起通过调用。

我希望这会有所帮助。

编辑：

如由发出呼叫的函数的末尾提及@dlasalle此代码可以由开到尾调用递归优化。

在这种情况下，您可以拥有以下版本。

int recurse_sum(int i, int j, int k, int sum) { 
     int res = .... // Logic for calculating sum for these indices i, j, k. 
     k++; 
     if (k==r) { 
      k = 0; 
      j++; 
     } 
     if(j==p){ 
      j=0; 
      i++; 
     } 
     if(i==q){ 
      return res + sum; 
     } 
     return recurse_sum(i,j,k,res+sum); 
} 

这里函数的结束是从内部调用返回值，因此可以很容易地进行优化。

Ofcourse在这种情况下，将有被称为recurse_sum(0,0,0,0);

Answer 3

感谢@ Jean-BaptisteYunès。

我对这些代码进行了更改，将其转换为递归。

#include<stdio.h> 
#define f(x, y, z) ((x + y)*(y + z)) 
int sum=0; 
void rec_k(int k,int r,int i,int j,int a[],int b[],int c[]) { // 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,a,b,c); 
} 

void rec_j(int j,int p,int i,int r,int a[],int b[],int c[]) { // j-loop 
    if (!(j<p)) return; 
    rec_k(0,r,i,j,a,b,c); 
    rec_j(j+1,p,i,r,a,b,c); 
} 

void rec_i(int i,int q,int p,int r,int a[],int b[],int c[]) { // i-loop 
    if (!(i<q)) return; 
    rec_j(0,p,i,r,a,b,c); 
    rec_i(i+1,q,p,r,a,b,c); 
} 
int main() { 
    int test_case, p, q, r, i, j, k, a[100001], b[100001], c[100001]; 
    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]); 
     } 
     rec_i(0,q,p,r,a,b,c); 
     printf("%d\n", sum%1000000007); 
    } 
    return 0; 
}