Javascript Question posted in
A very good W3school tutorial can be found here.

Recursion not resolving all the way back up (JavaScript)

I am currently trying to create a function that will take a position in the game of Tik-Tac-Toe and create a tree of all possible games from that position. The problem is that when I call the function it does not seem to resolve all the way back up.

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


}

I try the function by passing it an empty board and have it create a tree with all possible games that could arise from an empty board (The board is represented an array of chars with empty spaces being n, x spaces being represented with x, and o spaces being represented as o). here is the code where I do that

const board = []

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

root = new PostionNode(board);

createGameTree(root);

but when I run this the console output is

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?

Meaning that it only resolved up the recursive chain 1 time. Why is it not going all the way back up the chain?

Tags:

2

Answers


  1. 0

    So, you’re declaring avaliableMoves and childNode as global variables, where means each time recursive call is made, instead of having its own stack frame it’s going to be modifying the same data. It’s pretty obvious how that can lead to unpredictable, and certainly undesirable behavior.

    Change avaliableMoves = []; to let availableMoves = [];

    and

    childNode = new PostionNode(newPostion, currentNode); to let childNode = new PostionNode(newPostion, currentNode);

    When I tried that I got a much, much longer output, more in line with what you’d probably expect.

    Login or Signup to reply.
  2. 0

    try this

    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
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search