Counting elements of an array using a recursive function in JS

Question

I am going through the grokking algorithms book and trying to wrap my head around recursion. One of the challenges in the book is to "Write a recursive function to count the number of items in a list.". I came up with the following code, which works:

function recursiveArrayCount(arr, count) {
  if (arr.length == 0) {
    return 0;
  } else {
    arr.pop();
    return count + recursiveArrayCount(arr, count);
  }
}

let myArray = [1, 10, 23, 11, 4, 48, 88];
console.log(recursiveArrayCount(myArray, 1));

My question is, is there a better way to do this in javascript? In particular, I don't like having to seed the value of count with the initial '1' - but I can't think of another way to do it.

"is there a better way to do this in javascript": yes. This is not something you should use recursion for. For long arrays you will get a stack overflow error. Besides, your function is mutating the array with pop. That is not nice for the caller of your function, who will find after the call that their array has been destroyed. It is also strange to see code that attempts to count entries in an array without using the length property (which is the straightforward solution of course), but then still uses that property. — trincot
– trincot, Commented Jul 19, 2020 at 17:53
I agree with what trincot said in his comment. Using length property in a function that should calculate the length of the array without using the length property is strange. — Yousaf
– Yousaf, Commented Jul 19, 2020 at 19:02
I agree you would never do this in practice, it was just meant as an exercise in understanding recursion. I also agree that using arr.length was a poor choice given the role of the function. Changing it to if (arr == '') works and makes more sense. — crims0n
– crims0n, Commented Jul 19, 2020 at 20:31

Aplet123 · Accepted Answer · 2020-07-19 17:49:42Z

4

You don't need a second argument at all:

function recursiveArrayCount(arr) {
    if (arr.length == 0) {
        return 0;
    }
    return 1 + recursiveArrayCount(arr.slice(1));
}

answered Jul 19, 2020 at 17:49

Aplet123

35.8k1 gold badge41 silver badges66 bronze badges

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

9 Comments

T.J. Crowder Over a year ago

I also like using slice rather than modifying the original array. Another approach that dosen't require copying the array or modifying it is to change the if: if (arr.length <= count) { return count; }.

crims0n Over a year ago

Thank you! This is exactly what I was looking for - simple and eloquent.

Mulan Over a year ago

@T.J.Crowder but using arr.length is sort of a cheat... there'd be no reason to do counting if we can just access the length property...

crims0n Over a year ago

@Thank you, that was my mistake. if (arr == '') also works and makes more sense given the functions role.

T.J. Crowder Over a year ago

@Yousaf - Right, but that's a massive caveat, which is kind of my point. :-)

|

user12407908 · Accepted Answer · 2020-07-19 18:01:40Z

Make a proper tail call by eliminating any reference to variables that would be needed after the recursive call returns.

function recursiveArrayCount(arr) {
  return _recursiveCount(arr, 0);

  function _recursiveCount(arr, count) {
    return arr.length == 0 ? count : _recursiveCount(arr.slice(1), count + 1);
  }
}

let myArray = [1, 10, 23, 11, 4, 48, 88];
console.log(recursiveArrayCount(myArray));

This makes it more likely to be optimized by reusing stack space.

Also, I used a nested function for the recursion, which ensures that the count is properly initialized.

You could also get a little fancy with the inner function, like this:

function recursiveArrayCount(arr) {
  return (function _recursiveCount(arr, count) {
    return arr.length == 0 ? count : _recursiveCount(arr.slice(1), count + 1);
  })(arr, 0);
}

let myArray = [1, 10, 23, 11, 4, 48, 88];
console.log(recursiveArrayCount(myArray));

It's a recursively invoked IIFE.

Collectives™ on Stack Overflow

Counting elements of an array using a recursive function in JS

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related