admin管理员组文章数量:1317117
var count = 0;
var NumbOfNodes = function(root){
if(root.left != null){
NumbOfNodes(root.left);
}
count++;
if(root.right != null){
NumbOfNodes(root.right);
}
return count;
}
So I have this function that counts the number of nodes in a tree. It is a recursive function. When I make count a global variable, the function works and returns a proper value. The problem is, I want count to be part of the function. But if I declare count inside the function, it keeps on getting reset and I wont get a proper answer fro the function.
So, is there a way to preserve the value of a variable inside a recursive function. This question can help me in many other coding practices.
What I want (Diagram): Tree --> NumbOfNodes() --> gives me the number of nodes. But I don't want to make a global variable just for it.
Thanks!
var count = 0;
var NumbOfNodes = function(root){
if(root.left != null){
NumbOfNodes(root.left);
}
count++;
if(root.right != null){
NumbOfNodes(root.right);
}
return count;
}
So I have this function that counts the number of nodes in a tree. It is a recursive function. When I make count a global variable, the function works and returns a proper value. The problem is, I want count to be part of the function. But if I declare count inside the function, it keeps on getting reset and I wont get a proper answer fro the function.
So, is there a way to preserve the value of a variable inside a recursive function. This question can help me in many other coding practices.
What I want (Diagram): Tree --> NumbOfNodes() --> gives me the number of nodes. But I don't want to make a global variable just for it.
Thanks!
Share Improve this question edited Feb 12, 2018 at 5:47 Eddie 26.9k6 gold badges38 silver badges59 bronze badges asked Feb 12, 2018 at 5:46 PlzhelpPlzhelp 1854 silver badges13 bronze badges 1- 1 You can add an extra int parameter to your function, pass in 0 always to start. Then increment as normally would in function to count the nodes and return it. – JDSchenck Commented Feb 12, 2018 at 5:50
6 Answers
Reset to default 5Just return the count from within the recursion:
var NumbOfNodes = function(root) {
var count = 0;
if (root.left != null) {
count += NumbOfNodes(root.left);
}
count++; // count ourself
if (root.right != null) {
count += NumbOfNodes(root.right);
}
return count;
}
The basic idea here is that, at each step of the recursion, we start with a count of zero. Then we add to that count the number of nodes in the left and right subtrees, and we add one, to count ourself.
do you really need an extra variable to maintain count?
try this,
var NumbOfNodes = function(root){
if(!root){
return 0;
}
return NumbOfNodes(root.right) + NumbOfNodes(root.left) + 1;
}
you can pass the count
as an argument to that function like
var NumbOfNodes = function(root, count){
if(!count) count = 0;
if(root.left != null){
NumbOfNodes(root.left, count);
}
count++;
if(root.right != null){
NumbOfNodes(root.right, count);
}
return count;
}
Since NumOfNodes is a variable itself it is an instance and you can use this.count to cache itself as a value
var NumbOfNodes = function(root){
if (this.count === undefined) {
this.count = 0;
}
if(root.left != null){
NumbOfNodes(root.left);
}
this.count++;
if(root.right != null){
NumbOfNodes(root.right);
}
return this.count;
}
In order for the variable's value to be preserved, you need to pass it recursively. Something like:
var NumbOfNodes = numberOfNodes(roots, 0)
function numberOfNodes(root, count){
if(root.left != null){
numberOfNodes(root.left, count);
}
count++;
if(root.right != null){
numberOfNodes(root.right, count);
}
return count;
}
How to save a value to increment in a recursive function (Javascript)
Well you don't need to save a value in order to calculate the number of nodes. When designing a recursive function, just think about the base and inductive case(s)
- base case - the
node
is empty, return a count of 0 - inductive case - the
node
is not empty, return 1 for this node, plus the count of this node'sleft
andright
nodes.
Our countNodes
function almost writes itself
const Empty =
Symbol ()
const Node = (value = null, left = Empty, right = Empty) =>
({ Node, value, left, right })
const countNodes = (node = Empty) =>
node === Empty
? 0
: 1 + countNodes (node.left) + countNodes (node.right)
console.log
( countNodes () // 0
, countNodes (Node (0)) // 1
, countNodes (Node (0, Node (1), Node (2))) // 3
, countNodes (Node (0, Node (1, Node (2), Node (3))
, Node (4, Node (5), Node (6)))) // 7
)
本文标签: recursionHow to save a value to increment in a recursive function (Javascript)Stack Overflow
版权声明:本文标题:recursion - How to save a value to increment in a recursive function (Javascript) - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1742022349a2414909.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论