Recursive call instead of multiple for loop calls C++ [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

On the following example, with 5 loops I am able to obtain each individual index to access into multi dimensional array. Is there any way for dynamic systems if I don't know the dimension of the array, implement and recursive function to access the array. => Recursively implementing the for loop.

For Example:

index[3] = 0; //=> because it is 3 dimenional all are zero

void recursiveIndexWalk(int i){
    a[0] = i;
    recursiveIndexWalk(a[1]);
    //on the inner last recursive call a[index[0]][index[1]][index[2]] = val;

}

main(){
    //my goal is to perform instead of 3 for loops => only one   recursive() called
    recursive(a[0]);
}

---

unsigned int dimensions = 3;    //known 
unsigned int dimension_length = { 1, 2, 3}; //known

int a[1][2][3];

int counter = 0;
for (size_t r = 0; r < 1; r++)           //|
   for (size_t q = 0; q < 2; q++)        //| 
      for (size_t p = 0; p < 4; p++)     //| =>recursiveForCall(indexArray) 
           a[i][j][k] = counter++;

Answer 1

You could, for example, create a vector containing all the index IDs, so each in each recurse you add the index to the list before calling the recursive function then remove it from the list after.

However, it's probably a better idea to forgo the recursion idea here and instead just look at all the permutations using an iterative technique. Here's an arbitrary proof of concept, which should give you some ideas:

#include <stdio.h>

const unsigned int dimensions = 3;
const unsigned int dimension_size[dimensions] = { 2, 4, 3 };

// Get first permutation.
inline void get_first_permutation( unsigned int * const permutation )
{
    for ( int i = 0; i < dimensions; ++i )
        permutation[i] = 0;
}

// Returns false when there are no more permutations.
inline bool next_permutation( unsigned int * const permutation )
{
    int on_index = dimensions - 1;
    while ( on_index >= 0 )
    {
        if ( permutation[on_index] >= dimension_size[on_index] )
        {
            permutation[on_index] = 0;
            --on_index;
        }
        else
        {
            ++permutation[on_index];
            return true;
        }
    }
    return false;
}

// Print out a permutation.
void print_permutation( const unsigned int * const permutation )
{
    printf( "[" );
    for ( int i = 0; i < dimensions; ++i )
        printf( "%4d", permutation[i] );
    printf( "]\n" );
}

int main( int argc, char ** argv )
{
    // Get first permutation.
    unsigned int permutation[dimensions];
    get_first_permutation( permutation );

    // Print all permutations.
    bool more_permutations = true;
    while ( more_permutations )
    {
        print_permutation( permutation );
        more_permutations = next_permutation( permutation );
    }

    return 0;
}

This is, of course, assuming you actually need to know the indices. If you're just trying to update all the counters you can just loop from index 0 to index dim_0*dim_1*...*dim_n

/* Defined somewhere. Don't know how this gets allocated but what-evs. :) */
unsigned int dimensions = 5;
unsigned int dimension_length = { 1, 2, 4, 7, 6 };
int * int_array = ...

/* Your loop code. */
unsigned int array_length = 0;
for ( unsigned int d = 0; d < dimensions; ++d )
    array_length += dimension_length[d];
int *array_pointer = int_array;
for ( unsigned int i = 0; i < array_length; ++i, ++array_pointer )
    array_pointer = counter++;

Answer 2

If you don't need the indices as you traverse the array, you could treat it as a simple array. Using the known-size example above:

int * ap = ****a;
int n = 1 * 2 * 3 * 1 * 5;
for (size_t i = 0; i < n; ++i)
    *ap++ = counter++;

I'm not sure what a recursive implementation would buy you. It might blow the stack if the array is large.