Thread: what is the best method of tracing this code on paper..

it has loop one inside the other
which calls recursive of itself
many parameters.

its a nightmare to get the output on your own by pen and paper

Code:

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

 
int what1(int **arr, int m, int n); 
int what2 (int **arr, int row, int col, int m, int n);
int main()
{
	int ** arr=(int**)malloc(6*sizeof(int*));
	 

	*arr = malloc(5*sizeof(int));
    *(arr+1) = malloc(5*sizeof(int));
    *(arr+2) = malloc(5*sizeof(int));
    *(arr+3) = malloc(5*sizeof(int));
    *(arr+4) = malloc(5*sizeof(int));
    *(arr+5) = malloc(5*sizeof(int));

	arr[0][0]=0;
	arr[0][1]=1;
	arr[0][2]=1;
	arr[0][3]=0;
	arr[0][4]=1;
	
    arr[1][0]=0;
	arr[1][1]=0;
	arr[1][2]=1;
	arr[1][3]=0;
	arr[1][4]=0;

	 arr[2][0]=0;
	arr[2][1]=0;
	arr[2][2]=1;
	arr[2][3]=1;
	arr[2][4]=1;

 arr[3][0]=0;
	arr[3][1]=1;
	arr[3][2]=0;
	arr[3][3]=0;
	arr[3][4]=0;

 arr[4][0]=1;
	arr[4][1]=0;
	arr[4][2]=0;
	arr[4][3]=1;
	arr[4][4]=1;

 arr[5][0]=1;
	arr[5][1]=0;
	arr[5][2]=1;
	arr[5][3]=1;
	arr[5][4]=0;

what1(arr,6,5) ;
	return 0;
}

int what1(int **arr, int m, int n){
int i, j, tmp, stam=0;

for(i=0; i<m; i++)
for(j=0; j<n; j++){
   tmp = what2(arr,i,j,m,n);
   if (tmp>stam) 
         stam = tmp;
}
return stam;
}

int what2 (int **arr, int row, int col, int m, int n){
int i,j,tmp, stam=0;

if (row < 0 || row >= m || col < 0 || col >= n) return 0;
if (arr[row][col] == 0) return 0;
 

arr[row][col] = 0;
for(i=-1; i<2; i++)
	for(j=-1; j<2; j++){
		if(!i && !j) continue;
tmp = 1 + what2(arr, row+i, col+j, m, n);	
if (tmp > stam)  stam = tmp;
	}
arr[row][col] = 1;

return stam;
}

because i am asked to do that?

What you need to do is to break this down in its most simplest form. You know that you are allocating memory for a 6 x 5 array...right? So then you are needing to populate data into each of these int's that this matrix holds. This is accomplished with your for loops in your non-recursive call to your what1(). This function in tow does call the recursive function for what2().

1. Analyze what your for loops are trying to do.

2. Inspect your conditional statements, what constraints are they placing on the data?

3. Start by tracing the logic and writing down some pseudo code of this.

4. You may need to review recursive calls and how they place data on the stack...FILO

"What does it look like what1() does? "
it find the maximal member of all what what2() returns.

"What does it look like what2() does?"
it put 0 in the given cell
then i runs threw the close surrounding of the given cell
and does some recursive operation
and finds the maximal

Code:

       if(!i && !j) continue;
tmp = 1 + what2(arr, row+i, col+j, m, n);   
if (tmp > stam)  stam = tmp;
  
return stam;

"Can you break what2() into smaller, easier to understand pieces? "

Code:

if (row < 0 || row >= m || col < 0 || col >= n) return 0;
if (arr[row][col] == 0) return 0;

this is the end conditions

Code:

arr[row][col] = 0;
for(i=-1; i<2; i++)
   for(j=-1; j<2; j++){
      if(!i && !j) continue;
tmp = 1 + what2(arr, row+i, col+j, m, n);

it puts 0 into the original cell,and checks the surrounding of the cell
and does some recursive operation.

Code:

if (tmp > stam)  stam = tmp;
   }
arr[row][col] = 1;

return stam;

then we find the biggest tmp
put 1 in the original cell and return the biggest tmp.

"In what cases does it return 0? In what cases does it return nonzero?"
it returns 0 if the given cell is zero and when the indexes go beyond the array sizes.

so you whould just go like a debugger ??
or do some tree diagram??

the debugger method is too long i cant see how to make shortcuts in this proccess using these answered questions :

Code:

what1(arr,6,5) 
  |for(0<6)
  |for(0<5){
  |tmp = what2(arr,0,0,6,5);   //temp=0;
               |if (arr[row][col] == 0) return 0;
etc..
}

till n=4 and m=5 which is 30 times writing the proccess i did
and this the short return
there could be recursive calles to what2 itself
and all that for 30 times..

how to make shortcuts
??

what is the final case here?

so you would do this debugging method that i did
but not actually going to every function call
??

its still 30 general calls at least

i cant see how you start solving this?

regarding this code:

Code:

for(i=-1; i<2; i++)
	for(j=-1; j<2; j++){
		if(!i && !j) continue;
tmp = 1 + what2(arr, row+i, col+j, m, n);

i know that it checks the 8 surrounding cells
i know that the value of tmp will be at least 8
i cant what is the role of tmp

i dont know when what2 will return a value other then 0

??