recursion - How to save a value to increment in a recursive function (Javascript) - Stack Overflow

admin管理员组

文章数量:1317560

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!

• javascript
• recursion

Share Improve this question Follow edited Feb 12, 2018 at 5:47 Eddie 26.9k66 gold badges3838 silver badges5959 bronze badges asked Feb 12, 2018 at 5:46 PlzhelpPlzhelp 18544 silver badges1313 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

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 5

Just 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's left and right 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