JavaScript递归无法完全回溯：井字棋游戏树生成异常

问题现象 #

生成井字棋游戏树的递归函数无法完成完整回溯，控制台输出显示递归仅深入到叶子节点后回溯一次，无法回到上层循环处理其他可用移动路径。

原代码实现 #

PositionNode类 #

class PostionNode{
    constructor(postion, parent = null){
        this.postion = postion;
        this.parent = parent
        this.children = [];
    }
    get isLeaf(){
        return this.children.length === 0;
    }
    get hasChildren(){
        return !this.isLeaf();
    }
}

游戏树生成函数 #

function createGameTree(currentNode){
    avaliableMoves = [];
    let pieceTurnState;
    let xCount = 0;
    let oCount = 0;

    for(let i = 0; i < 9; i++){
        if(currentNode.postion[i] == 'x'){
            xCount++;
        }
        else if(currentNode.postion[i] == 'o'){
            oCount++;
        }
    }

    if(xCount == oCount + 1){
        pieceTurnState = 'o';
    }
    else if(oCount == xCount){
        pieceTurnState = 'x';
    }
    else{
        console.log("Non legal gamestate in createGameTree()");
        return null;
    }
    
    for(let i = 0; i < 9; i++){
        if(currentNode.postion[i] == 'n'){
            avaliableMoves.push(i);
        }
    }
    
    console.log("avaliableMoves length = ", avaliableMoves.length);
        
    for(let i = 0; i < avaliableMoves.length; i++){
        console.log("i = ", i);
        let newPostion = currentNode.postion.slice();
        newPostion[avaliableMoves[i]] = pieceTurnState;
        childNode = new PostionNode(newPostion, currentNode);
        currentNode.children.push(childNode);
        createGameTree(childNode);
        console.log("resolved?");
    }
}

测试代码 #

const board = []

for(let i = 0; i < 9; i++){
    board[i] = 'n';
}

root = new PostionNode(board);

createGameTree(root);

控制台输出 #

avaliableMoves length =  9
i =  0 
avaliableMoves length =  8
i =  0 
avaliableMoves length =  7
i =  0 
avaliableMoves length =  6 
i =  0 
avaliableMoves length =  5
i =  0
avaliableMoves length =  4
i =  0
avaliableMoves length =  3
i =  0
avaliableMoves length =  2
i =  0 
avaliableMoves length =  1
i =  0
avaliableMoves length =  0
resolved?

错误原因 #

核心问题是未声明变量导致的全局作用域污染：

• avaliableMoves和childNode未使用let/const声明，默认成为全局变量
• 递归过程中，下层调用会修改全局的avaliableMoves，当递归返回上层时，原来的可用移动列表已经被覆盖为下层的空数组
• 上层循环的条件i < avaliableMoves.length变为i < 0，直接终止循环，无法继续处理当前节点的其他子节点，导致仅回溯一次

修复方案 #

为未声明的变量添加let/const，使其成为递归函数的局部变量，避免不同递归调用间的变量干扰：

function createGameTree(currentNode){
    const avaliableMoves = []; // 添加const声明局部变量
    let pieceTurnState;
    let xCount = 0;
    let oCount = 0;

    for(let i = 0; i < 9; i++){
        if(currentNode.postion[i] == 'x'){
            xCount++;
        }
        else if(currentNode.postion[i] == 'o'){
            oCount++;
        }
    }

    if(xCount == oCount + 1){
        pieceTurnState = 'o';
    }
    else if(oCount == xCount){
        pieceTurnState = 'x';
    }
    else{
        console.log("Non legal gamestate in createGameTree()");
        return null;
    }
    
    for(let i = 0; i < 9; i++){
        if(currentNode.postion[i] == 'n'){
            avaliableMoves.push(i);
        }
    }
    
    console.log("avaliableMoves length = ", avaliableMoves.length);
        
    for(let i = 0; i < avaliableMoves.length; i++){
        console.log("i = ", i);
        let newPostion = currentNode.postion.slice();
        newPostion[avaliableMoves[i]] = pieceTurnState;
        const childNode = new PostionNode(newPostion, currentNode); // 添加const声明局部变量
        currentNode.children.push(childNode);
        createGameTree(childNode);
        console.log("resolved?");
    }
}

修复后，每个递归调用都会维护自己的avaliableMoves列表，递归返回上层后能继续处理当前节点的其他子节点，完成完整的回溯流程。

额外提示：类名PostionNode存在拼写错误，建议修正为PositionNode，避免后续维护混淆。

内容的提问来源于stack exchange，提问作者orcalord