Wie kann ich meine iterative Funktion in eine rekursive Funktion konvertieren?

Question

Ich möchte meine Funktion in eine rekursive Funktion verwandeln, weil ich denke, dass sie ein saubereres Aussehen haben wird, aber ich bin mir nicht sicher, wie ich das machen soll.

void perm_rec_1(int N, int nr_vals){ 
    int arr[N]; 
    int i=0; 
    while(i < N) 
    { 
    arr[i] = 0; 
    i++; 
    } 
    int k=0; 
    do { 
    int z=0; 
    while(z < N) { 
     printf("%d ",arr[z]); 
     z++; 
    } 
    printf("\n"); 
    k = N - 1; 
    while (k >= 0) { 
     arr[k]++; 
     if (arr[k] < nr_vals) { 
     break; 
     } 
     arr[k] = 0; 
     k--; 
    } 
    } while (k >= 0); 
} 

Answer 1

Erstens, wenn alles, was Sie wollen, ist ein sauberes Erscheinungsbild Sie können so etwas tun:

/* 
* prints all numbers in base base 
* will a number of digits up to num_digits 
*/ 
void perm_rec_1(int num_digits, int base) { 

    // create an array of size num_digits, initialize to 0 
    int arr[num_digits]; 
    int i=0; 
    while(i < num_digits) { 
    arr[i] = 0; 
    i++; 
    } 

    int current_digit=0; 
    do { 

    // print everything in arr on one line 
    int i=0; 
    while(i < num_digits) { 
     printf("%d ", arr[i]); 
     i++; 
    } 
    printf("\n"); 

    // reset the current digit to the rightmost digit 
    current_digit = num_digits - 1; 
    while (current_digit >= 0) { 

     // increment the current digit 
     arr[current_digit]++; 

     // if the current digit is less than the base 
     // go to the top of the loop (print the line) 
     if (arr[current_digit] < base) { 
     break; 
     } 

     // else reset the digit and shift it over one 
     arr[current_digit] = 0; 
     current_digit--; 

    } // end while 
    } while (current_digit >= 0); // end 'do' 
} 

Statt es ganz neu zu schreiben, denken Sie an einigen nützlichen Variablennamen. Eine der zeitaufwendigsten Fragen bei der Beantwortung dieser Frage war, herauszufinden, was es zu tun versuchte. Wenn Sie es vermeiden können, verwenden Sie niemals einzelne Zeichenvariablennamen. Denken Sie an etwas, das tatsächlich widerspiegelt, wofür die Variable verwendet wird. Kommentare sind auch gut, aber gute Variablennamen sind besser.

---

Jetzt, um tatsächlich Ihre Frage zu beantworten. Hier ist die rekursive Version des gleichen Programms:

void print_arr(int len, int* arr) { 
    int i; 
    for (i = 0; i < len; i++) { 
    printf("%d ", arr[i]); 
    } 
    printf("\n"); 
} 


void perm_rec_1_helper(int num_digits, int base, int curr_digit, int* arr) { 

    if (num_digits == curr_digit) { 
    print_arr(num_digits, arr); 
    return; 
    } 

    int i; 
    for (i = 0; i < base; i++) { 
    arr[curr_digit] = i; 
    perm_rec_1_helper(num_digits, base, curr_digit+1, arr); 
    } 

} 


void perm_rec_1(int num_digits, int base) { 
    int arr[num_digits]; 
    perm_rec_1_helper(num_digits, base, 0, arr); 
} 

Sehen Sie, ob Sie den Code durcharbeiten können, um es zu verstehen. Wenn Sie nicht können, werde ich eine Erklärung zu meiner Antwort hinzufügen.

Answer 2

Ich stimme den anderen zu, die angegeben haben, dass es am besten wäre, zuerst daran zu arbeiten, die Version mit Loops besser zu machen. Das Verbessern von Namen und Aufteilen von Aufgaben in Funktionen kann viel zur Klarheit Ihres Codes beitragen. Hier ist eine Version, die Schleifen verwendet. Ich habe versucht, die Aufgabe in kleinere Funktionen zu brechen in der Lesbarkeit zu unterstützen:

#include <stdio.h> 
#include <stdbool.h> 

void show_perms(size_t arr_sz, size_t nr_vals); 
void print_perm(size_t arr_sz, int arr[arr_sz]); 
bool next_array(size_t arr_sz, int arr[arr_sz], size_t nr_vals); 

int main(void) 
{ 
    size_t nr_vals; 
    size_t arr_sz; 

    printf("Enter number of values: "); 
    scanf("%zu", &nr_vals); 
    printf("Enter size of array: "); 
    scanf("%zu", &arr_sz); 

    show_perms(arr_sz, nr_vals); 

    return 0; 
} 

void show_perms(size_t arr_sz, size_t nr_vals) 
{ 
    int arr[arr_sz]; 

    for (int i = 0; i < arr_sz; i++) 
     arr[i] = 0; 

    do{ 
     print_perm(arr_sz, arr); 
    } while (next_array(arr_sz, arr, nr_vals)); 
} 

void print_perm(size_t arr_sz, int arr[arr_sz]) 
{ 
    for (int i = 0; i < arr_sz; i++) 
     printf("%d ", arr[i]); 
    putchar('\n'); 
} 

bool next_array(size_t arr_sz, int arr[arr_sz], size_t nr_vals) 
{ 
    int i; 

    for (i = (arr_sz - 1); i >= 0; i--) { 
     arr[i] = (arr[i] + 1) % nr_vals; 
     if (arr[i] != 0) 
      break; 
    } 

    if (i < 0) 
     return false; 
    else 
     return true; 
} 

Ich schrieb die oben Version zuerst, und verwenden es als Leitfaden in dieser rekursiven Lösung zu konstruieren. Zuerst hatte ich eine boolesche Funktion finished(), die überprüft, ob die aktuelle Permutation die letzte war, aber dann erkannte ich, dass die Änderung der index Variable von size_t zu index ermöglicht einen Wert von -1 zu halten, nachdem die endgültige Permutation gefunden wurde. Dies vereinfachte den rekursiven Code und zwang mich, die Schleifenlösung erneut zu betrachten, die auch eine Testfunktion namens is_another() hatte. Ich entfernte diese Funktion und änderte die next_array() Funktion, um true zurückzugeben, wenn es mehr Permutationen gibt, und false wenn nicht (wenn i negativ ist).

Die rekursive Lösung verwendet zwei gegenseitig rekursive Funktionen zum Erstellen und Drucken der Permutationen. Die Funktion print_permutations() lässt die Dinge beginnen, indem sie ein Array deklariert und auf Null setzt. Dann wird die print_perm()-Funktion aufgerufen, wobei zuerst die erste Permutation (alle Nullen) gedruckt wird und dann die next_perm()-Funktion aufgerufen wird. Diese Funktion ruft sich rekursiv selbst auf, bis die nächste Permutation gefunden wird, an der print_perm() erneut aufgerufen wird und alles neu beginnt. Dies wird so lange fortgesetzt, bis der Wert index -1 erreicht, woraufhin der letzte Aufruf an next_perm() zurückkehrt. Hier

#include <stdio.h> 

void print_permutations(size_t arr_sz, size_t nr_vals); 
void print_perm(size_t arr_sz, int arr[arr_sz], size_t nr_vals); 
void next_perm(size_t arr_sz, int arr[arr_sz], size_t nr_vals, int index); 

int main(void) 
{ 
    size_t nr_vals; 
    size_t arr_sz; 

    printf("Enter number of values: "); 
    scanf("%zu", &nr_vals); 
    printf("Enter size of array: "); 
    scanf("%zu", &arr_sz); 

    print_permutations(arr_sz, nr_vals); 

    return 0; 
} 

void print_permutations(size_t arr_sz, size_t nr_vals) 
{ 
    int arr[arr_sz]; 

    for (int i = 0; i < arr_sz; i++) 
     arr[i] = 0; 

    print_perm(arr_sz, arr, nr_vals); 
} 

void print_perm(size_t arr_sz, int arr[arr_sz], size_t nr_vals) 
{ 
    for (int i = 0; i < arr_sz; i++) 
     printf("%d ", arr[i]); 
    putchar('\n'); 

    next_perm(arr_sz, arr, nr_vals, (arr_sz - 1)); 
} 

void next_perm(size_t arr_sz, int arr[arr_sz], size_t nr_vals, int index) 
{ 
    if (index < 0) 
     return ; 

    arr[index] = (arr[index] + 1) % nr_vals; 
    if (arr[index] != 0) 
     print_perm(arr_sz, arr, nr_vals); 
    else 
     next_perm(arr_sz, arr, nr_vals, (index - 1)); 
} 

ist die Ausgabe von einem Probelauf:

Enter number of values: 2 
Enter size of array: 3 
0 0 0 
0 0 1 
0 1 0 
0 1 1 
1 0 0 
1 0 1 
1 1 0 
1 1 1