問題描述
為什麼我的遞歸沒有返回但最終導致堆棧溢出？ (Why does my recursion not return but end up in a stack overflow?)
First off, this is part of an extra credit homework, so please do not give me the answer. Please just help me understand where I might have a problem with what is going on. It is a Tic-Tac-Toe generator where the game goes through recursively to determine the best move based on the player. (Professor uses white 'W' and black 'B' instead of X and O)
My main recursive method returns the state score based on an input position on the TTT board; 1 if white will force a win from that position, 0 if it is a draw, and -1 if black will force a win from that position:
public int stateScore(boolean whiteMove, int[] BestMove) {
return stateScore(whiteMove,BestMove,TTTBoard);
}
which calls my underlying private recursion method:
private int stateScore(boolean whiteMove, int[] BestMove,char[][] TestBoard) {
char [][] newTestBoard = new char [3][3];
for(int rowVal = 0; rowVal < 3; rowVal++){
for(int colVal = 0; colVal < 3; colVal++){
newTestBoard[rowVal][colVal] = TestBoard[rowVal][colVal];
}
}
int [] bestMove = new int [2];
for(int rowVal = 0; rowVal < 3; rowVal++){
for(int colVal = 0; colVal < 3; colVal++){
if(isFull(newTestBoard) == true){
return 0;
}
else if(newTestBoard[rowVal][colVal] == '-'){
bestMove[0] = rowVal;
bestMove[1] = colVal;
//if boolean is white
if(whiteMove == true){
newTestBoard = testEntry(rowVal,colVal,'W',newTestBoard);
if(threeInRow(newTestBoard) == 1){
return 1;
}
else if(threeInRow(newTestBoard) == 0 && isFull(newTestBoard) == true){
return 0;
}
else if(threeInRow(newTestBoard) == -1 && isFull(newTestBoard) == true){
return -1;
}
else{
return stateScore(!whiteMove,bestMove,newTestBoard);
}
}
//if boolean is black
else{
newTestBoard = testEntry(rowVal,colVal,'B',newTestBoard);
if(threeInRow(newTestBoard) == -1){
return -1;
}
else if(threeInRow(newTestBoard) == 0 && isFull(newTestBoard) == true){
return 0;
}
else if(threeInRow(newTestBoard) == 1 && isFull(newTestBoard) == true){
return 1;
}
else{
return stateScore(!whiteMove,bestMove);
}
}
}
}
}
return 0;
}
The boolean value for whiteMove is true if it is white's move, and false if it is black's. Secondary methods within the function include threeInRow:
public int threeInRow(char[][] TTTBoard){
boolean whiteIs = false;
boolean blackIs = false;
//Horizontal?
char [] colChar = new char [3];
for(int rowVal = 0; rowVal < 3; rowVal ++){
for(int colVal = 0; colVal < 3; colVal++){
colChar[colVal] = TTTBoard[rowVal][colVal];
}
if(colChar[0] == colChar[1] && colChar[1] == colChar[2]){
if(colChar[0] == 'W'){
whiteIs = true;
}
if(colChar[0] == 'B'){
blackIs = true;
}
}
}
//Vertical?
char [] rowChar = new char [3];
for(int colVal = 0; colVal < 3; colVal ++){
for(int rowVal = 0; rowVal < 3; rowVal++){
rowChar[colVal] = TTTBoard[rowVal][colVal];
}
if(rowChar[0] == rowChar[1] && rowChar[1] == rowChar[2]){
if(rowChar[0] == 'W'){
whiteIs = true;
}
else if(rowChar[0] == 'B'){
blackIs = true;
}
}
}
//Diagonal
//topLeft to bottomRight
if(TTTBoard[0][0] == TTTBoard[1][1] && TTTBoard[1][1] == TTTBoard[2][2]){
if(TTTBoard[0][0] == 'W'){
whiteIs = true;
}
else if(TTTBoard[0][0] == 'B'){
blackIs = true;
}
}
//topRight to bottomLeft
if(TTTBoard[0][2] == TTTBoard[1][1] && TTTBoard[1][1] == TTTBoard [2][0]){
if(TTTBoard[1][1] == 'W'){
whiteIs = true;
}
else if(TTTBoard[1][1] == 'B'){
blackIs = true;
}
}
//Return Vals
if(whiteIs == true && blackIs == true){
return 0;
}
else if(blackIs == true && whiteIs == false){
return -1;
}
else if(blackIs == false && whiteIs == true){
return 1;
}
else if(blackIs == false && whiteIs == false){
return 0;
}
else{
return 0;
}
}
and testEntry:
public char[][] testEntry(int row,int col,char newChar, char[][] TestBoard){
char [][] returnBoard = new char[3][3];
for(int rowVal = 0; rowVal < 3; rowVal++){
for(int colVal = 0; colVal < 3; colVal++){
returnBoard[rowVal][colVal] = TestBoard[rowVal][colVal];
}
}
returnBoard[row][col] = newChar;
return returnBoard;
}
I don't understand where the stack overflow is coming from. It seems as though my returns cover all cases, and that my methods have appropriate returns. I haven't ever used a for loop with recursion, am I messing something up with that. Also, I am correct in saying that type [] name = name (same type) does NOT work, right? That is why I did the for loops in that case.
參考解法
方法 1:
In your black branch your return is wrong.
You return
return stateScore(!whiteMove,bestMove);
which restarts the recursion. You want to return
return stateScore(!whiteMove,bestMove,newTestBoard);
Hints:
Fix your booleans:
if(whiteMove == true) -> if (whiteMove)Use UpperCase for Classes, lowerCamelCase for variables.
If you return in an if branch, then you don't need an else.
Instead of:
if (condition) { ... return ...; } else { ... }It is better to write:
if (condition) { ... return ...; } ...Keeps the nesting lower and makes the code easier to follow.
Refactor common code: Both branches return the same result:
return stateScore(!whiteMove,bestMove,newTestBoard);Why not move this outside the if (whiteMove)
方法 2:
Post the stack trace, but I'd bet it is when you call stateScore recursively you are getting infinite recursion.
(by Zach Caudle、Christopher Oezbek、Garrett Hall)