Recursive javascript array length

Question

I'm trying to wrap my head around recursive functional programming concepts.

Consider the following scenario (yes, I could just use .length to get the array's length):

https://jsfiddle.net/ur5gc397/

$(function(){
  function arrLen(arr) {
    var count = 0;

    $.each(arr, function() {
      count = count + 1;
    });

    return count;
  }

  var a = ["a", "b", "c", "d"];

  var lengthOfA = arrLen(a);
})

I would like to rephrase this so that I'm not setting the variable count to 0, then mutating the value each time I iterate through my array. Can I set up some sort of function that recursively calls itself and then returns out of the function with the right value?

Answer 1

If you absolutely must test the length of an array recursively, you could do it like this:

function arrLen(arr) {
    if (!("0" in arr)) { // [].length is banned
        return 0;
    }
    return arrLen(arr.slice(0, -1)) + 1;
}

Please note that this is a really, really silly idea.

The idea is that, on each recursion, we slice off one element from the array (the last one, using slice(0,-1)) and return 1 more than whatever calling arrLen on the rest of the array returned.

The sequence looks something like this:

arrLen(["a", "b", "c", "d"])
    calls arrLen(["a", "b", "c"])
        calls arrLen(["a", "b"])
            calls arrLen(["a"])
                calls arrLen([])
                returns 0 == 0
            returns 0 + 1 == 1
        returns 0 + 1 + 1 == 2
    returns 0 + 1 + 1 + 1 == 3
returns 0 + 1 + 1 + 1 + 1 == 4

Answer 2

I just modified your code a bit:

$(function(){
  function arrLen(arr, count) {
  if(!arr[count]) return count;    
    count++;

    return arrLen(arr, count);
  }

  var a = ["a", "b", "c", "d"];
  var lengthOfA = arrLen(a, 1);

  $('body').html(lengthOfA)
})

Answer 3

For computing one value reduce is what to use. It's really not that special. Imagine you want to sum every element instead.

[1,2,3,4,5].reduce((a,e) => a+e, 0); // => 15

And reduce you can actually implement with recursion:

Array.prototype.myReduce = function(proc,init) {
  var arr = this;
  var nLen = this.length;
  function helper(acc, nIndex) {
    return nIndex >= nLen ?
           acc :
           helper(proc(acc, arr[nIndex]), nIndex+1); 
  }
  return helper(init, 0);
} 

[1,2,3,4,5].myReduce((a,e) => a+e, 0); // => 15

Note that an actual implementation wouldn't have used recursion since JS doesn't optimize tail calls and thus a looping construct would be more effiecent. Eg. Ramda is a functional library that provides means of making programs using compositions, but mapping and reductions in Ramda is implemented with loops.

EDIT

In the event you structure really isn't an array but something like a linked list then you need to check if you are at the end by checking if this is the singleton empty element. Here is an example implementation of a singly linked list with reduce, which looks thike the previous in this answer except the accessors and stop condition:

function List() {}

List.prototype.cons = function(a) {
  var c = new List();
  c.a = a;
  c.d = this;
  return c;
}

List.prototype.car = function() {
  return this.a;
}

List.prototype.cdr = function() {
  return this.d;
}

List.prototype.reduce = function(proc, init) {
  function helper (lst, acc) {
    return lst === emptyList ? 
           acc :
           helper(lst.cdr(), proc(acc, lst.car()));
  }
  return helper(this, init);
}

List.prototype.length = function() {
  return this.reduce(acc => acc+1, 0);
}

List.prototype.reverse = function() {
  return this.reduce((acc, a) => acc.cons(a),emptyList);
}

// Singleton empty list
window.emptyList = new List();

var example = emptyList.cons(1).cons(2).cons(9);
example.reduce((a,e)=>a+e,0); //=> 12
example.length(); // ==> 3
example.reverse(); // ==> (1,2,9)

Answer 4

If you want to use a for/forEach loop, then there's no place for recursion. Iteration and recursion are used to achieve the same result - you should choose one or the other.

Iteration:

Similar to your code just a bit simpler. Keep a count, increment and return it.

function arrayLength(array) {
  let count = 0;
  for (const i of array) count++;
  return count;
}

console.log(arrayLength([1, 2, 3, 4, 5]));
console.log(arrayLength([]));

Recursion:

Check if the next element in the array exists and if it does, keep calling the function recursively with the next index. The function returns the final index + 1, except for 0 which is special-cased. (Note well that this will not work for sparse arrays, as noted in the comments.)

function arrayLength(array, index) {
  index = index || 0;

  if (array[index+1]) {
    return arrayLength(array, index+1);
  } else if (index === 0) {
    return 0;
  } else {
    return index + 1;
  }
}

console.log(arrayLength([1, 2, 3, 4, 5]));
console.log(arrayLength([]));

Answer 5

You can do this using without using any for loop.

function arrLen(array, length=0) {
    if (array[0] === undefined) return length;
    length++;
    const newArray = array.slice(1);
    return arrLen(newArray, length)
}

var a = ["a", "b", "c", "d"];
var lengthOfA = arrLen(a);

First, I am trying to get the base case. My recursion will stop working once it finds that there is no element left in my array. When there is no element left in my array, then array[0] === undefined. I have initialized the length to zero so that I can increase my length value after each iteration and I did that using length++. My other target is to remove the first element from the array after each iteration, that's why I used the slice method. Then I used these new values of array and length in the returned function.