將嵌套循環轉換爲遞歸

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