如何將我的迭代函數轉換爲遞歸函數？

Question

我想把我的函數變成一個遞歸函數，因爲我認爲它會有一個更清晰的外觀，但我不知道如何去做。

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

首先，如果你想要的是你可能需要做這樣的事情看起來更簡潔：

/* 
* 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' 
} 

完全相反它重寫的，覺得一些有用的變量名。回答這個問題最耗費時間的部分之一是確定我們正在嘗試做什麼。如果您可以避免它，請勿使用單個字符變量名稱。想想一些實際反映變量被用於什麼的東西。評論也很好，但好的變量名稱更好。

---

現在，實際回答你的問題。這裏是同一個程序的遞歸版本：

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

看看你是否可以通過代碼來理解它。如果你不能，我會在我的答案中添加一些解釋。

Answer 2

我同意其他人表示最好先開始製作循環版本更好的版本。改進名稱和將任務分解爲函數可以幫助您清楚地瞭解代碼。這是一個使用循環的版本。我試圖打破任務分成更小的功能可讀性幫助：

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

我第一次寫了以上的版本，並將其作爲構建本遞歸解決方案的指南。起初，我有一個布爾函數finished()，檢查當前排列是否是最後一個排列，但後來我意識到將index變量從size_t更改爲int允許index在找到最終排列後保持值-1。這簡化了遞歸代碼，並讓我再次查看循環解決方案，該解決方案還具有稱爲is_another()的測試功能。我刪除了這個函數，並且如果有更多的排列，則將next_array()函數更改爲返回true，如果不是，則更改false（當i爲負數時）。

遞歸解決方案使用兩個相互遞歸的函數來構建和打印排列。函數print_permutations()通過聲明一個數組並將其歸零而使事情開始。然後調用print_perm()函數，首先打印第一個排列（全零），然後調用next_perm()函數。該函數遞歸調用自身，直到找到下一個排列，此時再次調用print_perm()，然後重新開始。這一直持續到index的值達到-1，此時最後一次呼叫next_perm()返回。

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

下面是一個示例運行的輸出：

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