CODEWITHSUNDEEP
pythonrecursion
zeyuxie
zeyuxie

Reputation: 75

a recursion function that return an int

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.

Upvotes: 0

Views: 1001

Answers (5)

Mulan
Mulan

Reputation: 135357

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

Upvotes: 0

PM 2Ring
PM 2Ring

Reputation: 55489

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)))

Upvotes: 0

niemmi
niemmi

Reputation: 17263

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)

Upvotes: 0

Sardorbek Imomaliev
Sardorbek Imomaliev

Reputation: 15400

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.

Upvotes: 1

clemens
clemens

Reputation: 17712

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.

Upvotes: 1

Related Questions