Konvertieren verschachtelte Schleife in Rekursion

Question

Ich habe 3 verschachtelte Schleife verwendet. Jetzt möchte ich diese Schleifen in rekursive konvertieren. Gibt es auch eine allgemeine Möglichkeit, eine Schleife in rekursive umzuwandeln?

#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

Eine Schleife wie genannt werden:

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

So:

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

als Rekursion übersetzt werden

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

kann übersetzt werden als:

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

Ich bin nicht sicher, dies entweder mehr lesbar oder nützlich ist, aber es erfüllt Ihre anfänglichen Bedürfnisse.

Answer 2

Nehmen wir an, dass die Absicht dieses Codes ist, nur die Summe zu berechnen.

Sie können eine Funktion als

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

machen Jetzt können Sie mit recurse_sum(0,0,0); Der Rest der Parameter können entweder aus global oder nur zusammen mit i, j, k nennen gerade passiert.

Ich hoffe, das hilft.

Edit:

Wie dieser Code von @dlasalle erwähnt, kann am Ende der Funktion, indem Sie den Anruf an Endrekursion Rekursion Optimierung offen gemacht werden.

In diesem Fall können Sie die folgende Version haben.

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

Hier endet die Funktion mit der Rückgabe des Wertes aus dem inneren Aufruf und kann somit einfach optimiert werden.

Ofcourse in diesem Fall wird es als Standard recurse_sum(0,0,0,0);

Answer 3

Dank @ Jean-Baptiste Yunès.

Ich habe diese Änderungen an meinem Code vorgenommen, um es in rekursive umzuwandeln.

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