How can I convert my iterative function to a recursive function?

Question

I want to turn my function into a recursive function because I think it will have a cleaner look to it, but I am not sure how to go about it.

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

I agree with the others who have indicated that it would be best to first work on making the version with loops better. Improving names and breaking tasks into functions can help a lot with the clarity of your code. Here is a version that uses loops. I have tried to break the task up into smaller functions to aid in readability:

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

I wrote the above version first, and used it as a guide in constructing this recursive solution. At first I had a boolean function finished() that checked to see if the current permutation was the final one, but then I realized that changing the index variable from size_t to int allows index to hold a value of -1 after the final permutation is found. This simplified the recursive code, and made me look at the loop solution again, which also had a test function called is_another(). I removed this function and changed the next_array() function to return true if there are more permutations, and false if not (when i is negative).

The recursive solution uses two mutually recursive functions to build and print the permutations. The function print_permutations() gets things started by declaring an array and zeroing it out. Then the print_perm() function is called, first printing the first permutation (all zeroes), and then calling the next_perm() function. This function recursively calls itself until the next permutation is found, at which point print_perm() is called again, and everything starts over. This continues until the value of index reaches -1, at which point the last call to next_perm() returns.

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

Here is the output from a sample run:

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 

Answer 2

First, if all you want is a cleaner look you may want to do something like this:

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

Instead of rewriting it entirely, think of some more useful variable names. One of the most time consuming parts of answering this question was figuring our what it was trying to do. If you can avoid it, never use single character variable names. Think of something that actually reflects what the variable is being used for. Comments are good too, but good variable names are better.

---

Now, to actually answer your question. Here is the recursive version of the same program:

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

See if you can work through the code to understand it. If you cannot, I will add some explanation to my answer.