递归无法一路解析（JavaScript）

Question

我目前正在尝试创建一个函数，该函数将在 Tik-Tac-Toe 游戏中占据一个位置，并从该位置创建一个包含所有可能游戏的树。问题是，当我调用该函数时，它似乎并没有完全解决。

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?");
    }


}

我通过向其传递一个空板来尝试该函数，并让它创建一棵树，其中包含空板可能产生的所有可能的游戏（该板表示一个字符数组，其中空格为 n，x 空格用 x 表示， o 空格表示为 o)。这是我这样做的代码

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?

这意味着它只解析了递归链 1 次。为什么它没有一路回到链条上？

Answer 1

因此，您将

avaliableMoves

和

childNode

声明为全局变量，这意味着每次进行递归调用时，它不会拥有自己的

stack frame

，而是会修改相同的数据。很明显，这会导致不可预测的、当然也是不良的行为。

将

avaliableMoves = [];

更改为

let availableMoves = [];

和

childNode = new PostionNode(newPostion, currentNode);

至

let childNode = new PostionNode(newPostion, currentNode);

当我尝试时，我得到了更长的输出，更符合您的预期。

Answer 2

试试这个

function createGameTree(currentNode){
    let 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;
        let childNode = new PostionNode(newPostion, currentNode);
        currentNode.children.push(childNode);
        createGameTree(childNode);
        console.log("resolved?");
    }
    
    return currentNode; // return the current node
}