How to count instances of numbers in an array using recursion?

Question

I try to write a function (called: tally) using recursion (part of the exercise) to scan through an array of numbers and return an object with the numbers as key and the number of instances as value.

Example:

tally([2,3,4,5,5,5,5,5,5,5,6,7,,6,7,6,7,5,4,3,4,5,5,6])
//{2: 1, 3: 2, 4: 3, 5: 10, 6: 4, 7: 3}

I created the framework but i am not sure about the syntax to make it work:

function tally(arr) {
    var obj = {}
    if (/*check if object ('obj') has a key corresponding to the array element*/) {
        //increase key's value by onee
    } else {
        //add key with value of 1
    }
    return obj
};

Any hints to complete the recursion function above? Please try to stick to my structure in your answers as much as possible since this is part of an exercise.

It doesn't make any sense at all to use recursion here, it only makes things (much) more confusing than they need to be. Do you have to create a new obj on each call, and can the tally function only accept that one arr argument, or can those be changed? — CertainPerformance
– CertainPerformance, Commented Oct 11, 2019 at 0:39
To make it recursive you need to track the counts, the ever-shortening array of remaining values, and a check to know when you're done. — Dave Newton
– Dave Newton, Commented Oct 11, 2019 at 0:42
If you want to use recursion, you need to decide what to recurse over and what the base case will be. That'll be the framework for your recursive function. Then fill in the base case and the recursion step with logic. — Bergi
– Bergi, Commented Oct 11, 2019 at 0:43
@Stephan-thecurious Can you show us how those looked? They have a particular structure that you will need to replicate in tally. — Bergi
– Bergi, Commented Oct 11, 2019 at 0:54

Charlie · Accepted Answer · 2019-10-11 00:58:35Z

1

Here you are:

function tally(arr) {
    if (arr.length == 0) {
        return {}
    }
    var value = arr.pop()
    var obj = tally(arr)
    if (value in obj) {
        obj[value] += 1
    } else {
        obj[value] = 1
    }
    return obj
};

EDIT: It can also be done using slice() instead of pop():

function tally(arr) {
    if (arr.length == 0) {
        return {}
    }
    var value = arr[0]
    var obj = tally(arr.slice(1))
    if (value in obj) {
        obj[value] += 1
    } else {
        obj[value] = 1
    }
    return obj
};

edited Oct 11, 2019 at 0:58

answered Oct 11, 2019 at 0:49

Charlie

1674 bronze badges

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

5 Comments

Stephan - the curious Over a year ago

hmmm ... I haven't covered "pop" yet, so this shouldn't be part of my code (even if it might be right or best practice)

Bergi Over a year ago

@Stephan-thecurious Do you know about slice()? If not, then you would have to recurse over arrays indices, which is weird.

Stephan - the curious Over a year ago

Yeah, slice is covered

Stephan - the curious Over a year ago

As a hint for the exercise I have "The || operator can be handy here..."

Charlie Over a year ago

@Stephan-thecurious I've updated the answer with the slice() approach

Mulan · Accepted Answer · 2019-10-12 02:44:20Z

1

Using extra parameter for an index, i, the result, r -

const plus1 = (k = "", r = {}) =>
  ( k in r
      ? r[k] += 1
      : r[k] = 1
  , r
  )

const tally = (a = [], i = 0, r = {}) =>
  i >= a.length
    ? r
    : tally
        ( a
        , i + 1
        , plus1(a[i], r)
        )

console.log(tally([2,3,4,5,5,5,5,5,5,5,6,7,,6,7,6,7,5,4,3,4,5,5,6]))

Output

{
  "2": 1,
  "3": 2,
  "4": 3,
  "5": 10,
  "6": 4,
  "7": 3,
  "undefined": 1
}

edited Oct 12, 2019 at 2:44

answered Oct 11, 2019 at 4:40

Mulan

136k35 gold badges240 silver badges276 bronze badges

4 Comments

Scott Sauyet Over a year ago

Do you choose the index parameter over a slice-based version chiefly for performance? Or do you see this simpler than a version that uses a recursive call such as tally(xs.slice(1), ...)?

Mulan Over a year ago

The majority of my answers exist as a way of seeing the problem solved in another way because this is an effective learning tool for myself. I was going to use destructing assignment but the original question has a sparse input. I then thought about writing a long-format answer to address the issue but then landed on this one instead. The added parameter and [...] notation is noisy, but it does offer good performance. Other answers show use of .slice so I figured the OP would be made familiar with that technique. I hope all readers can learn something from each answer provided ^^

Ry- Over a year ago

Performance that’s immediately thrown away by copying r for every item. This is quadratic (in the worst case – specifically Ө(mn) on m = number of distinct elements and n = number of elements).

Mulan Over a year ago

Ry thank you for keeping me honest. I think my edit fixes the problem.

ffflabs · Accepted Answer · 2019-10-11 00:55:29Z

0

ok, so you are asked to do a recursion just for the sake of it.

This could be done (albeit is hacky) passing an extra parameter to tally. When you declare a function in vanilla js you can actually feed it extra stuff. So, in each recursion, pass obj as a second parameter:

EDIT Thanks @Bergi, you're right. I'll edit the code

function tally(arr) {
    let obj = arguments.length>1? arguments[1] : {};
    if(arr.length===0) {
      return obj;
    }
    let next_number=arr.pop();
    obj[next_number]=obj[next_number]||0;
    obj[next_number]++;
    
    return tally(arr,obj);
};

let inputArr = [2,3,4,5,5,5,5,5,5,5,6,7,6,7,6,7,5,4,3,4,5,5,6],
outputObj=tally(inputArr);
console.log(outputObj);
console.log({outputEmpty:tally([])});

edited Oct 11, 2019 at 0:55

answered Oct 11, 2019 at 0:50

ffflabs

17.6k5 gold badges57 silver badges79 bronze badges

1 Comment

ffflabs Over a year ago

It depends on what you consider "homework". Every one of us that codes for a living does sooner or later rely on StackOverflow, so completing a homework through SO is actually preparing him for the actual job experience

Tucker Sneed · Accepted Answer · 2019-10-11 01:02:38Z

0

I am not sure how to guide you to an answer without giving it away entirely, but this is what I would recommend. (There are some problems such as you destroy arr in the process that you may want to consider)

function tally(arr, obj) {

    // if the length is zero we've gone through every value
    if(arr.length === 0)
        return obj

    // create obj if we didn't provide it
    if(obj === undefined)
        obj = {}

    // pull the last value from arr
    let val = arr.pop()

    if (/*check if object ('obj') has a key corresponding to the array element*/) {
        //increase key's value by onee
    } else {
        //add key with value of 1
    }

    // move onto the next value
    return tally(arr,obj)

}

EDIT: took @Bergi's input

edited Oct 11, 2019 at 1:02

answered Oct 11, 2019 at 0:58

Tucker Sneed

214 bronze badges

1 Comment

Bergi Over a year ago

Better check for arr.length than whether the val is undefined.

Collectives™ on Stack Overflow

How to count instances of numbers in an array using recursion?

4 Answers 4

5 Comments

4 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

4 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related