Playing with recursion and ways to visualize it. And recursive tree traversal.

recursionDrawingAttempt1.js

/////////////////////////////////////////////////////////////////////////////////////
// Using code from recursionExample.js, modifying it to try to visualize with p5js
// ToC:
//  - animateRecursivelyAddToTen(sum, frameQueue)
//  - drawFrame(frameQueue, currentIndex)
//  - Params for drawing, global vars: counter for clicks, frameQueue
//  - Set up event listener and run clickHandler > run drawFrame
//  - Set up p5js (setup() and unused draw() function)
/////////////////////////////////////////////////////////////////////////////////////

function animateRecursivelyAddToTen(sum, frameQueue) {
  console.log("called animateRecursivelyAddToTen with: " + sum);
  
  // Push each value into a queue, return the queue 
  frameQueue.push(sum);
 
  // Base case: when sum reaches 10, stop recursing!
  if (sum >= 10) {
    console.log("sum >= 10");

  } else {
  
    sum = animateRecursivelyAddToTen(sum + 1, frameQueue);

    // The next lines only run AFTER all calls have been added
    // to the stack. They'll run for each call that has been
    // resolved, AFTER sum has already reached the base case.
          // console.log("sum: " + sum);
    
    return frameQueue;
  }
}

// On every click, draw visualization based on frameQueue
function drawFrame(frameQueue, currentIndex) {
 
    let currentValue = frameQueue[currentIndex];
  
    // Coordinates for drawing: move from top to bottom:
    let x = initialX;
    let y = initialY + currentIndex * (nodeSize + margin);
  
    // Clear each frame
    clear();
    
    // Draw a circle
    fill( "lightblue" );
    ellipse(x, y, nodeSize, nodeSize);

    // Draw currentValue as text in the circle
    fill("black");
    // Set text size to no more than 60% of the nodeSize, or less based on number of digits
    let numDigits = currentValue.toString().length;
    textSize( Math.min(nodeSize/numDigits, nodeSize*0.6) );
    textFont("Arial");
    textAlign(CENTER, CENTER);
    text(currentValue, x, y);

}


// Params for drawing:
const canvasWidth = 900, canvasHeight = 500;   // canvas dimensions
const nodeSize = 30;                           // given as diameter of each node
const margin = 10;                             // minimum margin between nodes
const initialX = nodeSize + margin;
const initialY = nodeSize + margin;



// RUN ALGO FUNCTION ONCE
// and save output (frame queue) to use for drawing function
let frameQueue = animateRecursivelyAddToTen(0, []);
// Global var, easy for tracking # of clicks to iterate through frameQueue
let counter = 0;

console.log("framequeue: " );
console.log(frameQueue);

// Run drawFrame() on each mouse click, iterating through frameQueue
document.addEventListener("click", handleClick);

function handleClick() {
  counter++;
  let currentIndex = counter % frameQueue.length;
  drawFrame(frameQueue, currentIndex);
  
  console.log("Click count: " + counter);
  console.log("Current index: " + currentIndex);
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////
// SETUP FOR P5JS DRAWING:
////////////////////////////////////////////////////////////////////////////////////////////////////////////

function setup() {
  
  // Fix for retina disaplys (bug: claer() only clears top left corner of canvas)
  pixelDensity(1);
  
  createCanvas(canvasWidth, canvasHeight);

  // 2 frames per second, easier for testing :)
  // frameRate(2);
  
  noLoop();
}

// Loops for animation, FPS controlled by frameRate() -- default is up to 60 if supported?
function draw() {

} // end draw()

// function mousePressed() {
//   //iterations++;
//   redraw();
// }

recursionExamples.js

/////////////////////////////////////////////////////////////////////////////////////
// First, a couple quick examples of a recursive function, to use for reference
/////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////
// EXAMPLE 1: Output a simple sum
/////////////////////////////////////////////////////////////////////////////////////

function recursivelyAddToTen(sum) {
  console.log("called recursivelyAddToTen with: " + sum);
  if (sum >= 10) {
    console.log("sum >= 10");
    
    // This is how we resolve the LAST (most recent) function call
    // We must return sum here, to preserve the final value. Otherwise,
    // after the last call is resolved, sum will be set to "undefined"
    // and then the final output will be "undefined"!
    return sum;    
  }
  
  // Need to do this so that lines after this function call
  // will "remember" the final sum; otherwise, final val will be 0!
  sum = recursivelyAddToTen(sum + 1);

  // The next lines only run AFTER all calls have been added
  // to the stack. They'll run for each call that has been
  // resolved, AFTER sum has already reached the base case.
  console.log("sum: " + sum);
  
  // This runs for EVERY functon call, and this is how we can
  // remember" the final sum, and how we return it at the very end
  return sum;
}

recursivelyAddToTen(0);

/////////////////////////////////////////////////////////////////////////////////////
// EXAMPLE 2: Output an array of values
/////////////////////////////////////////////////////////////////////////////////////

function recursivelyAddToTenArray (sum, collection) {
  console.log("called recursivelyAddToTenArray with: " + sum);
  
  // Push each value to array
  collection.push(sum);
  
  if (sum >= 10) {
    console.log("sum >= 10");
    
    // In this case, it doesn't matter what we return, as long as we stop recursing!
    // Because all other function calls already have a POINTER to the same array stored in memory
    // That's an important difference between this example and example 1 (outputting a sum).
    // ALTERNATE VERSION: don't need to call return here at all! Replace with an if/else structure.
    return;
  }
    
  // NOTE: don't need to do anything like sum = recursiveCall(sum+1) here, because
  // we don't need to remember the final value of sum! We already have a pointer to
  // the modified-in-place array!
  // ...So I think if this used an immutable array instead, we would need to do
  // collection = recursiveCall(sum+1, collection);
  recursivelyAddToTenArray(sum + 1, collection);

  // The next lines only run AFTER all calls have been added
  // to the stack. They'll run for each call that has been
  // resolved, AFTER sum has already reached the base case.
  console.log("sum: " + sum);
  console.log(collection);
  
  // This runs for EVERY functon call, and this is how we
  // return the final output at the very end
  return collection;
}

recursivelyAddToTenArray(0, []);

/////////////////////////////////////////////////////////////////////////////////////
// EXAMPLE 3: Output an array of values, using an IMMUTABLE array style
// NOTE: But I think this isn't a good solution, because it takes up A TON of memory,
//       with all those extra copies of the array!
/////////////////////////////////////////////////////////////////////////////////////

function recursivelyAddToTenArray (sum, collection) {
  console.log("called recursivelyAddToTenArray with: " + sum);
  
  // Push each value to array
  collection = [...collection, sum];
  
  if (sum >= 10) {
    console.log("sum >= 10");
    
    // In this case, it doesn't matter what we return, as long as we stop recursing!
    // Because all other function calls already have a POINTER to the same array stored in memory
    // That's an important difference between this example and example 1 (outputting a sum).
    // ALTERNATE VERSION: don't need to call return here at all! Replace with an if/else structure.
    return collection;
  }
    
  // NOTE: don't need to do anything like sum = recursiveCall(sum+1) here, because
  // we don't need to remember the final value of sum! We already have a pointer to
  // the modified-in-place array!
  // ...So I think if this used an immutable array instead, we would need to do
  // collection = recursiveCall(sum+1, collection);
  collection = recursivelyAddToTenArray(sum + 1, collection);

  // The next lines only run AFTER all calls have been added
  // to the stack. They'll run for each call that has been
  // resolved, AFTER sum has already reached the base case.
  console.log("sum: " + sum);
  console.log(collection);
  
  // This runs for EVERY functon call, and this is how we
  // return the final output at the very end
  return collection;
}

recursivelyAddToTenArray(0, []);

workInProgress-7-20.js

let tree1 = {
    "value": "01",
    "leftChild": {
        "value": 10,    
    },
    "rightChild": {
        "value": 11
  }        
};

let tree2 = {
    "value": 1,
    "leftChild": {
        "value": 10,
    "leftChild": {
                "value": 100
            },
            "rightChild": {
                "value": 101
            }
    },
    "rightChild": {
        "value": 11,
    "leftChild": {
                "value": 110
            },
            "rightChild": {
                "value": 111
            }
    }
};





function recursiveSumDepthFirst (currentNode, sum) {
  console.log("--------------------------");
      
  sum += currentNode.value;

  console.log("Currently on: " + currentNode.value);
  //console.log("New sum: " + sum);

    if (currentNode.leftChild) {
      console.log("Left child exists. Recursing!");
      sum = recursiveSumDepthFirst(currentNode.leftChild, sum);
    }
    
    if (currentNode.rightChild) {
      console.log("Right child exists. Recursing!");
      sum = recursiveSumDepthFirst(currentNode.rightChild, sum);
    }
  
  return sum;
  
}


let stuff = recursiveSumDepthFirst(tree2, 0);

console.log(stuff);








// function recursiveCollectionDepthFirst (currentNode, collection) {
//   console.log("--------------------------");
      
//   collection.push(currentNode.value);

//   console.log("Currently on: " + currentNode.value);
//   //console.log("New sum: " + sum);

//     if (currentNode.leftChild) {
//       console.log("Left child exists. Recursing!");
//       recursiveCollectionDepthFirst(currentNode.leftChild, collection);
//     }
    
//     if (currentNode.rightChild) {
//       console.log("Right child exists. Recursing!");
//       recursiveCollectionDepthFirst(currentNode.rightChild, collection);
//     }
  
//   return collection;
  
// }


// let stuff = recursiveCollectionDepthFirst(tree2, []);

// console.log(stuff);




// function recursiveSumDepthFirst (currentNode, sum) {
//   console.log("--------------------------");
    
//   if (!currentNode || sum >= 200) {
//     console.log("No more nodes I guess? Returning null");
//     return sum;
//   }
  
//     sum += currentNode.value;

//   console.log("Currently on: " + currentNode.value);
//   console.log("New sum: " + sum);

//     if (currentNode.leftChild) {
//       console.log("Left child exists. Recursing!");
//       recursiveSumDepthFirst(currentNode.leftChild, sum);
//     }
    
//     if (currentNode.rightChild) {
//       console.log("Right child exists. Recursing!");
//       recursiveSumDepthFirst(currentNode.rightChild, sum);
//     }
  
//     return sum;
  
// }


// recursiveSumDepthFirst(tree2, 0);





function recurseDepthFirst (currentNode, valueToFind) {
  console.log("--------------------------");
  
  let foundValue = null;
  
  if (!currentNode) {
    console.log("No more nodes I guess? Returning null");
    return foundValue;
  }
  
  console.log("Currently on: " + currentNode.value);
  
  if (currentNode.value === valueToFind) {
    console.log("MATCH!!!!");
    return currentNode.value;
    
  } else {
  
    if (currentNode.leftChild) {
      console.log("Left child exists. Recursing!");
      foundValue = recurseDepthFirst (currentNode.leftChild, valueToFind);
    }
    
    if (currentNode.rightChild) {
      console.log("Right child exists. Recursing!");
      foundValue = recurseDepthFirst (currentNode.rightChild, valueToFind);
    }
  
    return foundValue;
  
  }
  
  
}


// recurseDepthFirst(tree2, 110);