🔒 Locked

[java] Problem with recursion

Started by cordel Feb 25, 2009 at 5:20 AM 4 replies 1.4k views

Original Post

Feb 25, 2009 at 5:20 AM

Hello people , I need some help with a recursion code . The task is : I have a NxN board ,filled with numbers between [0-9]. When the user writes : " public static int[][] fill(int[][] map, int x, int y, int cc) " the board ,from the coordinate (x,y) , would start feeling each relative coordinate to (x,y) , with the number that stored in the variable "cc" I wrote the code , but I have a non ending loop and i can't figure out what to do.I've tried change it over and over again , but nothing. I'll appreciate any help or hint you can add , thanks in advance . Here is the code : the non recurcive method "fill" calls the recurcive method "fill_And_Not_Return" . The "not1,not2" variables resresents the previous coordinate that "I was" , so when I go to its next neighbor , I will not go again to the coordinate which I was at . Can I add pictures in this forum ? to clarify the problem ?


    public static int[][] fill(int[][] map, int x, int y, int cc)
     {
          int n = map.length - 1;
          fill_And_Not_Return(map,x,y,-1,-1,n,cc);
          return map;
     }
     
     
     public static void fill_And_Not_Return (int [][]map,int x ,int y,int not1,int not2,int n,int cc)
     
     {
     	
     	if (x==0 & y==0)   // left up corner  - MAX 2 neighbors
     	{
     		
     		if (0!=not1 |1!=not2 && legalNeighbor(map,x,y,0,1)==true)
     			fill_And_Not_Return(map,0,1,x,y,n,cc);
     			
     		if (1!=not1 | 0!=not2 && legalNeighbor(map,x,y,1,0)==true)
     			fill_And_Not_Return(map,1,0,x,y,n,cc);   
     		 		
     		map[x][y]=cc;
     		
     		
  
     	}

     	if (y==0 & x>0 & x<n)  // the middle of the first line   - MAX 3 neighbors
     	{
     		
     		if (x-1!=not1| y!=not2 && legalNeighbor(map,x,y,x-1,y)==true)
     			fill_And_Not_Return(map,x-1,y  ,x,y,n,cc);
     			
		if (x!=not1 | y+1!=not2 && legalNeighbor(map,x,y,x,y+1)==true)
			fill_And_Not_Return(map,x,y+1  ,x,y,n,cc); 
					
		if (x+1!=not1 | y!=not2 && legalNeighbor(map,x,y,x+1,y)==true)
     			fill_And_Not_Return(map,x+1,y  ,x,y,n,cc);
     		
     		map[x][y]=cc;
  
     	}
     	
 
           	

        if (y>0 & y<n & x==0)       // left column  - MAX 3 neighbors (not the corners!!!)
        {
        	
            if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
        		fill_And_Not_Return(map,x,y-1  ,x,y,n,cc);
            
            if (x+1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x+1,y)==true)
            	fill_And_Not_Return(map,x+1,y  ,x,y,n,cc);
             
            if (x!=not1 | y+1!=not2 && legalNeighbor(map,x,y  ,x,y+1)==true)
            	fill_And_Not_Return(map,x,y+1  ,x,y,n,cc);
            	
            map[x][y]=cc;
           
        }
        
        
        
        
  
        
 	    if (y>0 & y<n & x==n)    // right column - MAX 3 neighbors (not the corners!!!)
 	    {
 	    	if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
 	    		fill_And_Not_Return(map,x,y-1 ,x,y,n,cc);
 	    		
 	    	if (x-1!=not1 |y!=not2 && legalNeighbor(map,x,y  ,x-1,y)==true)
 	    		fill_And_Not_Return(map,x-1,y ,x,y,n,cc);
              
                if (x!=not1 | y+1!=not2 && legalNeighbor(map,x,y  ,x,y+1)==true)
                	fill_And_Not_Return(map,x,y+1 ,x,y,n,cc);
            	
                map[x][y]=cc;               	    		 	     	    	 	    	
 	    }        
 	    
      	if (y==n & x==0)     // down left corner - 2 MAX
       	{
       		if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
       			fill_And_Not_Return(map,x,y-1 ,x,y,n,cc);
		if (x+1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x+1,y)==true)
			fill_And_Not_Return(map,x+1,y ,x,y,n,cc);
       	   
       	   map[x][y]=cc;               	    		 	     	    	 	    	
       	}
        
       	if (x==n & y==n)   // down right corner  - 2 MAX
       	{
       		if (x-1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x-1,y)==true)
       			fill_And_Not_Return(map,x-1,y ,x,y,n,cc);
       		if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
       			fill_And_Not_Return(map,x,y-1 ,x,y,n,cc);
       			
       	    map[x][y]=cc;   
       	}
       	
    	if ( y==n & x>0 & x<n )  // the middle of the last line            // 3 MAX 
     	{
     		if (x-1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x-1,y)==true)
     			fill_And_Not_Return(map,x-1,y ,x,y,n,cc);
     		if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
     			fill_And_Not_Return(map,x,y-1 ,x,y,n,cc);
     		if (x+1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x+1,y)==true)
     			fill_And_Not_Return(map,x+1,y ,x,y,n,cc);
            
            map[x][y]=cc;        			
     	}
     	
     	
     	
         /*   If the program got here ,the point is somethere inside the matrix */
     	
     	   if (x>0 && x<n && y>0 && y<n)
     	   {
     	   
     	   
            if (x-1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x-1,y)==true)
            	   fill_And_Not_Return(map,x-1,y,x,y,n,cc);
           	   	
     	    if (x!=not1 | y-1!=not2 && legalNeighbor(map,x,y  ,x,y-1)==true)
     	    	   fill_And_Not_Return(map,x,y-1 ,x,y,n,cc);
     	   	
       	    if (x+1!=not1 | y!=not2 && legalNeighbor(map,x,y  ,x+1,y)==true)	
     	        fill_And_Not_Return(map,x+1,y ,x,y,n,cc);
     	       
            if (x!=not1 | y+1!=not2 && legalNeighbor(map,x,y  ,x,y+1)==true)	
            	   fill_And_Not_Return(map,x,y+1 ,x,y,n,cc);
           	   
           map[x][y]=cc;        
        
     	   }
             	
     	
       	
        
     }  // end of fill_and_not_return

rip-off

Mod

445

rip-off

Feb 25, 2009 at 5:29 AM

Have you looked at how others have solved this?

In Java, a single apersand is the bitwise AND operator. Logical and is two amersands, &&. Likewise logical or is ||, not |.

cordel

Author

cordel

Feb 25, 2009 at 5:40 AM

Quote:
Original post by rip-off
Have you looked at how others have solved this?

In Java, a single apersand is the bitwise AND operator. Logical and is two amersands, &&. Likewise logical or is ||, not |.

Okay ,my lecturer taught me only with one |,&

and not two . Nonetheless I've looked into the double || && and I'll start using it from now on.

I've checked the others ,but I'm trying to fix mine.Can you see where is the problem ? I've debugged for the last day or so , changed /added/ - and gurnisht( "gurnisht" is Yiddish for "nothing" )

rip-off

Mod

445

rip-off

Feb 25, 2009 at 5:52 AM

Quote:

I've checked the others ,but I'm trying to fix mine.

Very admirable [smile]

Well, we can't give very specific help with homework questions, its against the forum rules.

But here is something that would greatly simplify your code: reduce the number of bounds conditions. What you could do is allow the function to call itself with x and y out of bounds - just don't take any action:

void fill(int [][] map, int x, int y, /* ... */, int value){     if(x >= 0 && y >= 0 && x < width(map) && y < height(map))     {         // recursively call these co-ordinates:         // x, y + 1         // x, y - 1         // x + 1, y         // x - 1, y     }}

Also it appears your "not" parameters are attempting to make sure the function never visits somewhere it has already been. But this won't work because you only remember the previous neighbour. Your system can form larger loops, like so:

1 --> 2^     ||     ||     .4 <-- 3

I believe it is loops like this that are currently causing your function to enter an infinite recursion.

You need some better way to not revisit a previously visited co-ordinate.

Lord_Evil

Feb 25, 2009 at 8:29 AM

Quote:
Original post by rip-off
Have you looked at how others have solved this?

In Java, a single apersand is the bitwise AND operator. Logical and is two amersands, &&. Likewise logical or is ||, not |.

Just to clarify that: you can use &, &&, | and || in logical operations. For boolean operands the result is (almost the same).

Difference: With & and | ALL statements are evaluated before returning the result. && and || are "early out" operators, meaning that only those statements are evaluated that are needed to determine the result. So if x = 1 and y = 0, in (x == 0 && y == 0) only x == 0 is evaluated, whereas y == 0 is skipped since it would not change the result. (That's why there is no ^^ [smile].)

So, generally it is best to use && and ||. But if you always need all operands to be evaluated first use & and |.

cordel

Author

cordel

Feb 26, 2009 at 3:22 AM

Thank you everyone , I've solved the problem with my method.My sincere gratitude to all you guys :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.