admin管理员组文章数量:1317123
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.
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.
Share Improve this question asked Jun 19, 2016 at 20:17 jmancherjejmancherje 6,6338 gold badges38 silver badges59 bronze badges 02 Answers
Reset to default 7A 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.
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;
}
本文标签:
版权声明:本文标题:javascript - Recursive function, maintain a global counter without using a global variable - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1742021165a2414701.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论