-2

I'm given an assignment to define a function def count_occurrences(lst, num): where I need to find the number of times of occurrences of a number num within a list lst. The difficult part is that lists can be nested in lists, and I need to keep digging to the lowest level of each list to count the occurrences. For example, count_occurrences([1, [2, 1], 1, [3, [1, 3]], [4, [1], 5], [1], 1, [[1]]], 1) returns 8. Here is my current function:

def count_occurrences(lst, num):
    if type(lst[0]) != list:
        if lst[0] == num:
            return 1
        else:
            return 0
    else:
        count_occurrences(lst[0], num) + count_occurrences(lst[1:], num)

But I realised that this function does not quite work. One reason is that in some cases, lists only have one element, so the index will go beyond range. In addition, in the above example to count occurrences of 1 returns 1 only, not 8.

Can anyone provide any advice in this case? Any help is much appreciated!

a9302c
  • 239
  • 1
  • 6
  • 1
    you could just flatten the list first and then use Counter from the itertools module. have a look here at how to flatten an irregularly nested list https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists – LukasNeugebauer Mar 09 '22 at 09:00
  • 2
    Whatever you do, you must ``return`` on the recursive call as well! – MisterMiyagi Mar 09 '22 at 09:07
  • @MisterMiyagi Oh dear, good catch! – a9302c Mar 09 '22 at 09:09
  • 2
    Don't just check the first element (that's a logical error) and don't walk through the list by recursing on slices (that's *very* inefficient). You should *iterate* over the entire list, then *recurse* if an element is a list and add the result or *increment* when an element equals the desired number. Always return the total over the entire list. – MisterMiyagi Mar 09 '22 at 09:12

1 Answers1

0

You could use a recursive function:

def count_occurrences(lst, num):
    counter = 0
    for lst_i in lst:
        if isinstance(lst_i, list):
            counter += count_occurrences(lst_i, num)
        elif lst_i == num:
            counter += 1
    
    return counter

If the input to the function is a list, you forward it into itself. If the input is a number, and it matches your target you increase the counter.

dzang
  • 2,160
  • 2
  • 12
  • 21
  • Why do you need to pass the counter to the recursive call? Why not simply count the occurrences in the recursive element and add the result? `counter += count_occurrences(...)` – Pranav Hosangadi Mar 09 '22 at 09:35
  • indeed you don't need to do that :) It was just less confusing for me, but it works even without that. I modified the answer as you suggested – dzang Mar 09 '22 at 09:38