How to save a value to increment in a recursive function (Javascript)

Question

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!

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
– JDSchenck, Commented Feb 12, 2018 at 5:50

Tim Biegeleisen · Accepted Answer · 2018-02-12 05:55:11Z

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.

edited Feb 12, 2018 at 5:55

answered Feb 12, 2018 at 5:50

Tim Biegeleisen

526k32 gold badges324 silver badges399 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Plzhelp Over a year ago

Hmm, this is the best solution to this so far, Thanks so much!

Ravindra Thorat · Accepted Answer · 2018-02-12 06:00:32Z

1

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; 
}

edited Feb 12, 2018 at 6:00

answered Feb 12, 2018 at 5:52

Ravindra Thorat

2,0021 gold badge18 silver badges25 bronze badges

Comments

Aswin Ramesh · Accepted Answer · 2018-02-12 05:53:55Z

0

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;
}

answered Feb 12, 2018 at 5:53

Aswin Ramesh

1,6741 gold badge13 silver badges13 bronze badges

Comments

Chris · Accepted Answer · 2018-02-12 05:55:47Z

0

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;
}

answered Feb 12, 2018 at 5:55

Chris

1,0331 gold badge10 silver badges23 bronze badges

Comments

meow2x · Accepted Answer · 2018-02-12 06:12:29Z

0

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;
 }

answered Feb 12, 2018 at 6:12

meow2x

2,13425 silver badges27 bronze badges

Comments

Mulan · Accepted Answer · 2018-02-12 22:50:19Z

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
  )

Collectives™ on Stack Overflow

How to save a value to increment in a recursive function (Javascript)

6 Answers 6

1 Comment

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related