c - 如何将迭代函数转换为递归函数？

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

与其完全重写它，不如考虑一些更有用的变量名。回答这个问题最耗时的部分之一是弄清楚我们想要做什么。如果可以避免，切勿使用单字符变量名。考虑一些实际反射(reflect)变量用途的东西。注释也不错，但是好的变量名更好。

---

现在，实际回答您的问题。这是同一程序的递归版本:

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

看看您是否可以通过代码来理解它。如果你不能，我会在我的回答中添加一些解释。