递归溢出问题

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 直到你运行进入 WhosebugError!

改为前缀递增：

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;

递归溢出问题

Overflow issue with recursion

java

recursion