在 c 语言中将嵌套的 for 循环转换为递归

Question

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
          //  0  1  2  3  4  5  6  7
int arr[] = { 3, 6, 1, 2, 6, 7, 8, 4};
int bee[] = { 6, 8, 1, 4, 2, 6, 3, 7};
int i = 0;
int j = 0;
int matches[120] = {0};
int length1 = 8;

void find_matches(int *arr, int *bee, int*matches);

void find_matches(int *arr, int *bee, int *matches)
{
    for (i = 0; i<length1; i++)
    {
        for (j = 0; j < length1; j++)
        {
            if (arr[i]==bee[j])
            {
                matches[i] = j;
            }
        }
    }

    for (int z = 0; z<8; z++)
    {
        printf("%d\n", matches[z]);
    }
}

int main()
{
    find_matches(arr, bee, matches);
}

The gist of my code is that it is matches every value of arr[] to bee[] and puts the index of the matches as numbers in the matches arrays and prints.

For example the value 3 in arr[0] is matched to the value 3 in bee[5] so the value of matches[0] will be 5.

How can I turn this into a recursive function?

I tried keeping the outer for loop and running the outer with a recursion function call inside but I don't know how to set up the variables and such.

转载于:https://stackoverflow.com/questions/53111823/convert-a-nested-for-loop-into-recursion-in-c

Answer 1

Twofold recursion, over both arrays - see the comments:

// recursives
void find_matches(int *arr, int *bee, int *matches, int current_position_in_arr);
void find_matches_in_bee(int *arr, int *bee, int *matches, int current_position_in_arr, int current_position_in_bee);

// wrapper
void find_matches(int *arr, int *bee, int *matches) {
    find_matches(arr, bee, matches, 0);
}

// outer loop : iterate over 'arr'
void find_matches(int *arr, int *bee, int *matches, int current_position_in_arr) {
    // check where arr[current_position_in_arr] is present in bee
    find_matches_in_bee(arr, bee, matches, current_position_in_arr, 0);

    // "next iteration of loop" - we check the next element in arr
    if (current_position_in_arr + 1 < length) {
        find_matches(arr, bee, matches, current_position_in_arr + 1);
    }
}

// inner loop : iterate over 'bee'
void find_matches_in_bee(int *arr, int *bee, int *matches, int current_position_in_arr, int current_position_in_bee) {
    // do your business magic
    if (arr[current_position_in_arr] == bee[current_position_in_bee]) {
       ....
    }

    // "next iteration of loop" - we check the next element in bee
    if (current_position_in_bee + 1 < length) {
        find_matches_in_bee(arr, bee, matches, current_position_in_arr, current_position_in_bee + 1);
    }
}

Invoke the same way as before:

find_matches(arr, bee, matches);

---

The lesson here is that you can replace stuff like:

int *array;

for (int i = 0; i < LEN; ++i) {
  f(array[i]);
}

with

void f(int *array) {
  f_inner(array, 0);
}

void f_inner(int *array, int position) {
  // business logic on array[position]

  // iteration step
  if (position + 1 < LEN) {
    f_inner(array, position + 1);
  }
}