如何将我的迭代函数转换为递归函数？

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