a recursion function that return an int

Question

def nested_count(l : 'any nested list of int', a : int) -> int:
    c = 0
    while len(l) != 0:
        for x in l:
            if type(x) == int:
                if x == a:
                    c = c + 1
                    l.remove(x)
                    nested_count(l,a)
                else:
                    continue 
            elif type(x) == list:
                nested_count(x,a)
    return c

this function passed a nested list of ints and a single int as arguments; it returns the number of times the single int argument appears in the nested list argument, for example:

nested_count( [[1,2,[4,[1],8],[1,3,2]],[1,1]], 1 )

returns 5

I am not sure why my function does not work

can someone tell me how to fix it? many thanks.

You need to return the result of the recursive function call. For example `return nested_count(l,a)` — thefourtheye, Oct 31 '16 at 06:47

score 1 · Answer 1 · answered Oct 31 '16 at 06:49

1

The results of the nested function calls are not used. You probably should replace the lines with c += nested_count(l,a) and c += nested_count(x,a), respectively.

answered Oct 31 '16 at 06:49

clemens

16,716
11
50
65

score 1 · Accepted Answer · answered Oct 31 '16 at 06:55

You are not adding nested_count results to c:

def nested_count(lst, l):
    c = 0
    for i in lst:
        if i == l:
            c += 1
        elif type(i) == list:
            c += nested_count(i, l)
    return c

Also it is better to iterate over list with for.

score 0 · Answer 3 · answered Oct 31 '16 at 06:56

You shouldn't mutate the list while iterate over it and you need to return the result from recursive calls. You could simplify function greatly by checking the type of l and if it's int then returning bool telling if it matches with a. In case l is a list just call nested_count recursively on its' items and sum the result:

def nested_count(l, a):
    # Base case
    if type(l) == int:
        return l == a
    return sum(nested_count(x, a) for x in l)

Mulan · Answer 4 · 2016-11-01T20:41:12.303

Why the heterogenous list? Why bother using typing if you're not going to type all the parameters? Why are you mutating the input?

from typing import List

def deep_count_elem (x:int, xs:List) -> int:
  # done
  if len(xs) == 0:
    return 0
  # if list, count in this list and recurse
  elif isinstance(xs[0], list):
    return deep_count_elem(x, xs[0]) + deep_count_elem(x, xs[1:])
  # if element matches, add 1
  elif x == xs[0]:
    return 1 + deep_count_elem(x, xs[1:])
  # otherwise add nothing, move to next element
  else:
    return deep_count_elem(x, xs[1:])

print(deep_count_elem(1, [[1,2,[4,[1],8],[1,3,2]],[1,1]])) # 5

score 0 · Answer 5 · edited May 23 '17 at 11:48

As others have mentioned you need to accumulate the return values from the recursive calls of nested_count to get the correct total.

Also, removing items from a list (or other collection) that you're iterating over can lead to unexpected results, see the SO Python Common Question Removing items from a list while iterating over the list for details and a few relevant SO pages, in particular: Removing from a list while iterating over it.

It's generally preferred to call isinstance rather than type to do type testing. The isinstance function can test for multiple types in one call, it will also return True if the object is a subclass of the specified type.

Here are a couple of one-liners that handle lists or tuples.

def nested_count(l, a):
    return sum(nested_count(x, a) if isinstance(x, (list, tuple)) else x == a for x in l)

and

def nested_count(l, a):
    return l.count(a) + sum(nested_count(x, a) for x in l if isinstance(x, (list, tuple)))

a recursion function that return an int

5 Answers5