遞歸溢出問題

Question

我有一些java代碼來爲地圖的所有區域着色，而沒有任何相鄰區域着色相同的顏色。但是，我遇到了我似乎無法解決的溢出錯誤。任何幫助是極大的讚賞。

import java.util.*; 
import java.io.*; 

class Guthrie{ 

    static int[][] adjMat; 
    static char[] color; 
    static int regions; 

/**main method that initiates the rest of the program 
Pre-Cond: user enters valid inputs when prompted 
Post-Cond: print of all regions and colors 
responses: error terminate 
@return void*/ 
    public static void main(String[] args)throws FileNotFoundException{ 
     Scanner kbd = new Scanner(System.in); 
     System.out.println("Please enter the following."); 
     System.out.println("Filename to read?: "); 
     String fileName = kbd.next(); 
     System.out.println("Number of regions?: "); 
     regions = kbd.nextInt(); 
     adjMat = new int[regions][regions]; 
     color = new char[regions]; 
     reader(fileName); 
      for(int i=0; i<regions; i++){ 
       color[i] = 'f'; 
      } 
     if(colorReg(0)){ 
      for(int i=0; i<regions; i++){ 
       if(color[i] == 'r') System.out.println("Region " + i + " is red."); 
       else if(color[i] == 'o') System.out.println("Region " + i + " is orange."); 
       else if(color[i] == 'y') System.out.println("Region " + i + " is yellow."); 
       else if(color[i] == 'g') System.out.println("Region " + i + " is green."); 
      } 
     } 
     else System.out.println("Incompatible Map."); 
     kbd.close();  
    } 

    /**reads a user supplied file 
    Pre-Cond: fileName is a valid String with a file by that String's name present 
    Post-Cond: none 
    responses: FileNotFoundException 
    @param fileName - A user supplied String for a file name 
    @return void*/ 
    public static void reader(String fileName)throws FileNotFoundException{ 
     Scanner sc = new Scanner(new FileReader(fileName)); 
     for(int i=0; i<regions; i++){ 
      String row=sc.nextLine(); 
      String[] splits=row.split(" "); 
      for(int j=0; j<regions; j++){ 
       splits[j] = splits[j].trim(); 
      } 
       for(int j = 0; j<regions; j++){ 
       adjMat[i][j] = Integer.parseInt(splits[j]); 
      }   
     } 
     sc.close(); 
    } 

    /**checks if any adjacent regions are the same color as v 
    Pre-Cond: v < regions and a valid integer 
    Post-Cond: boolean true or false 
    responses: error terminate 
    @param v - region number 
    @return boolean*/ 
    public static boolean checkColor(int v){ 
     for(int i=0; i<regions; i++){ 
      if(adjMat[v][i] == 1){ 
       if(color[v] == color[i]) return false; 
      } 
     } 
     return true; 
    } 

    /**recursively backtracks to color map without adjacent regions having the same color 
    Pre-Cond: v < regions and a valid integer 
    Post-Cond: boolean true or false 
    responses: error terminate 
    @param v - region number 
    @return boolean*/ 
    public static boolean colorReg(int v){ 
     if(filled()) return true; 
     for(int i=0; i<4; i++){ 
      switch(i){ 
       case 0:{ 
        color[v] = 'r'; 
        if(checkColor(v)) break; 
       } 
       case 1:{ 
        color[v] = 'o'; 
        if(checkColor(v)) break; 
       } 
       case 2:{ 
        color[v] = 'y'; 
        if(checkColor(v)) break; 
       } 
       case 3:{ 
        color[v] = 'g'; 
        if(checkColor(v)) break; 
       } 

      } 
     } 
     if (colorReg(v++)) return true; 
     v--; 
     color[v] = 'f'; 
     return false; 
    } 

    /**checks if every region has been colored 
    Pre-Cond: none 
    Post-Cond: boolean true or false 
    responses: error terminate 
    @return boolean*/ 
    public static boolean filled(){ 
     for(int i=0; i<regions; i++){ 
      if(color[i] == 'f') return false; 
     } 
     return true; 
    } 

} 

Answer 1

你colorReg()方法調用本身：

if (colorReg(v++)) return true; 

這將同一v值傳遞給後續的遞歸調用，因爲你使用後綴增量，將與同一區域工作。並且不會隨着地區進展，而是會陷入初始v=0，直到遇到StackOverflowError！

將其更改爲前綴增量：

if (colorReg(++v)) return true; 
v--; 

或明確+1在這種情況下，你不需要後開始減少它：

if (colorReg(v + 1)) return true; 
// No need v-- 

Answer 2

它看起來像你傳遞相同的值的v，因爲您使用的是後綴增量運算符，因此可以調用colorReg()的每個遞歸調用。

而不是

if (colorReg(v++)) return true; 
    v--; 

嘗試

if (colorRef(v+1)) return true;