CODEWITHSUNDEEP
python-3.x
Rohit
Rohit

Reputation: 6020

Counting instances of N in an array using Recursion in Python

I would like to count the number of instances of a given number N in an array using recursion. For example, given: 

array = [1, 2, 3, 1, 1, 4, 5, 2, 1, 8, 1]

and N = 1, the function should return 5.

This problem can be solved using the .counter attribute as shown here. However, I am looking to not use any in-built functions or attributes.

Here's my attempt to solve this using recursion but I get a count of 1 and not 5. What am I doing wrong? 

def count_val(array, n, count=0):
    if len(array) == 0:
        return None
    # Base Case
    if len(array) == 1:
        if array[0] == n:
            count += 1
    else:
        count_val(array[1:], n, count)
        if array[0] == n:
            count += 1
    return count

print(count_val2(array, 1))

1

Upvotes: 0

Views: 619

Answers (2)

Djaouad
Djaouad

Reputation: 22794

I think for an empty array, the value should be 0 (len == 0 should be the base case), and, you don't need to have a count parameter if you just return the count, your function could be reduced to this:

def count_val(array, n):
    if len(array) == 0:
        return 0
    return (array[0] == n) + count_val(array[1:], n)

array = [1, 2, 3, 1, 1, 4, 5, 2, 1, 8, 1]

print(count_val(array, 1))

Output:

5

You can have it as a one-liner as well (as suggested by @blhsing):

def count_val(array, n):
    return len(array) and (array[0] == n) + count_val(array[1:], n)

Upvotes: 2

melbok
melbok

Reputation: 95

What am I doing wrong?

The function you wrote will always keep only the last few characters, so after a while it will be [1, 8, 1], after that [8, 1] and after that [1], which returns 1. The array never contains just any of the other 1s.

An easy way to do this is to loop over all elements in a list and test if they are equal to N.

array = [1, 2, 3, 1, 1, 4, 5, 2, 1, 8, 1]

def count_val(array, n):
    if len(array) == 0:
        return 0
    count=0
    for i in array:
        if i==n:
            count += 1
    return count

print(count_val(array, 1))

This returns 5.

Upvotes: 0

Related Questions