CODEWITHSUNDEEP
javascriptrecursionecmascript-6
jmancherje
jmancherje

Reputation: 6633

Recursive function, maintain a global counter without using a global variable

I'm writing functions to serialize and deserialize a binary tree (just converting it to an array and back to a BT) and I'm having a hard time writing the deserializing function without using a global variable to keep track of the index.

my Node class looks like this:

class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

and my serialize method looks like this:

function serialize(node = this, list = []) {
  if (!node) {
    list.push('#')
    return
  }

  list.push(node.value)
  serialize(node.left, list)
  serialize(node.right, list)
  return list
}

Here's my problem, in the deserialize function I have to keep a global variable for the 'index', is there a way to keep the global value for the index without creating a global variable?

let index = 0

function deserialize(list) {
  if (index === list.length || list[index] === '#') {
    index++
    return
  }

  const tree = new Node(list[index])
  index++

  tree.left = deserialize(list)
  tree.right = deserialize(list)

  return tree
}

I initially wrote the function like this: (but I had to refactor the index variable to a global variable)

function deserialize(list, index = 0) {
  if (index === list.length || list[index] === '#') {
    index++
    return
  }

  const tree = new Node(list[index])
  index++

  tree.left = deserialize(list, index)
  tree.right = deserialize(list, index)

  return tree
}

This ended up with a symetric tree because the tree.left and tree.right would always take the same index.

I'm just curious if there is a simple way to keep track of the index in a purely recursive function (not using a recursive subroutine) without creating a global variable.

Upvotes: 3

Views: 2333

Answers (2)

Pointy
Pointy

Reputation: 413757

A general way to do that:

function wrapperFunction(args) {
  var bookkeepingStuff = whatever;
  function actualRecursiveFunction(args) {
    // code
  }

  return actualRecursiveFunction(args);
}

Just wrap the real recursive function in another function. Any local variables of the wrapper will be effectively like global variables to the real recursive function nested inside.

Upvotes: 7

Eric
Eric

Reputation: 97601

Pass a baton with a member you can update as you recurse:

function deserialize(list, baton={index: 0}) {
  var b = baton;  // shorthand
  if (b.index === list.length || list[b.index] === '#') {
    b.index++;
    return;
  }

  const tree = new Node(list[b.index]);
  b.index++;

  tree.left = deserialize(list, b);
  tree.right = deserialize(list, b);

  return tree;
}

Upvotes: 4

Related Questions