Recursion-Backtracking in C function arguments

[aliakmonas]

Hi i am having the following problem:

I am using Recursion in C.

Clearly i have a function like that:


void Test(int times,int Array[5][5])
{
times++;
for (i=0;i<3;i++)
Test(times,Array[5][5]);
}

My problem: i cannot get 'earlier' versions of the 2-dimensional array when i do backtracking, while with times
that is possible.

Can i make the array hold the earlier values it had when the recursion goes back (without of course using a stack)

 

[Salem]

Well you have to create a copy of the array at each step

void Test(int times,int Array[5][5])
{
   int CopyArray[5][5];
   /* copy Array to CopyArray say */
   times++;
   for (i=0;i<3;i++)
     Test(times,CopyArray);
}

Each nested caller has it's own personal copy of the array which isn't messed about with by any other nested call to the function.

--

 

[aliakmonas]

Trust me i have tried it and still does not work.

The CopyArray is changed as well as we pass it as a parameter to a function.

Maybe it is not possible every nested caller to have its personal copy, what do you think?

 

[marsd]

Am I missing something?

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>

#define MAX 10
#define DING 5

void popArray(int *);
void testRecur(int *, int*);

int main(void) {
int foo = 0;
int array[DING][DING];
int *ptr = (int *)&array;
                         
			 srand(time(NULL));
			 popArray(ptr);
			 testRecur(&foo,ptr);
return 0;
}

void popArray(int *foo)  {
int j = 0;

           while (j < DING) {foo[j] = (int)(1 + rand() % MAX); j++;}
}

void testRecur(int *cntr, int *array) {
int p;
              printf("Cntr value = %d\n",*cntr);
              if (*cntr < MAX) {
	         for (p=0 ; p < DING ; p++) {printf("\t%d at %d\n",array[p],p);}
		     popArray(array);
		     *cntr += 1;
		     return testRecur(cntr,array);
                 }
return;
}

 

[Salem]

> Maybe it is not possible every nested caller to have its personal copy, what do you think?
Unless you post your actual code, I'm saying no more.

As far as I'm concerned, there is no reason why what I suggested would not work.


--

 

[Salem]

Something like this

#include <stdio.h>
#include <stdlib.h>

void PrintArray ( int a[3][3] ) {
  int r, c;
  for ( r = 0 ; r < 3 ; r++ ) {
    for ( c = 0 ; c < 3 ; c++ ) {
      printf( "%d ", a[r][c] );
    }
  }
  printf( "\n" );
}
void FillArray ( int a[3][3], int value ) {
  int r, c;
  for ( r = 0 ; r < 3 ; r++ ) {
    for ( c = 0 ; c < 3 ; c++ ) {
      a[r][c] = value;
    }
  }
}
void recursive ( int a[3][3], int level ) {
  int local[3][3];

  FillArray( local, level );
  FillArray( a, level );
  if ( level == 4 ) return;

  /* both these are the same */
  printf( "Before at level %d\n", level );
  PrintArray( local );
  PrintArray( a );

  recursive( local, level + 1 );

  /* local array is updated, parameter array isn't */
  printf( "After  at level %d\n", level );
  PrintArray( local );
  PrintArray( a );
}

int main ( ) {
  int array[3][3] = { { 0 } };
  recursive( array, 1 );
  return 0;
}

--

 

[aliakmonas]

Thanks for replies but i solved the problem

I was true i could not pass the 2-dimensional array to a
function as an argument and hoping that this array would be a local variable to the function.

So, what i did actually was the following:

Have the array as a global variable:

int Array[8][8];

and then after every recursive call undo all the changes done
to the array before:

Test()
{

Do changes to array Array[8][8];

Test();

Undo the changes to array Array[8][8];

}


As for your curiosity the probles was the 8-queens problem, but it could also be a maze problem.

Nikos