How to properly use recursion on nested lists in python?

Question

I am 4 weeks into programming with python and now we are talking about recursion.

Problem statement

I need to write a function with one parameter which is a list; the function must check if the list and its sublists satisfy the criteria:

all elements in the list are ints;

OR

all elements in the list are lists,
AND all sublists also satisfy the criteria.

For example:

[1, 2]                 True
[[1, 2, [1]]]          False
[[1], [2], [[3], [1]]] True

And so on.

My attempt so far

I tried to check the width first and then go into the depth. Go level per level deeper. But this wont work because at some point this

[[1], [2], [[3], [1]]]

goes to

1, 2, [3], [1]

which is wrong.

I realised i need to go into the depth first and if I can't go deeper and checked everything I need to go back. Something like a binary tree. And there is my problem. I don't know when I am deep and finished to come back to my "leftover" list.

def intSuperListe(list_to_check):
    for idx, item in enumerate(list_to_check):
        if idx + 1 < len(list_to_check):
            if type(list_to_check[idx]) == type(list_to_check[idx + 1]):
                if type(list_to_check[idx]) == int:
                    if len(list_to_check) == 1 or len(list_to_check) == 2:
                        return True
                    else:
                        continue
                elif type(list_to_check[idx]) == list:
                    intSuperListe(list_to_check[idx])
                return True
            return False
        elif type(list_to_check[idx]) == int:
            return True
        elif type(list_to_check[idx]) == list:
            intSuperListe(list_to_check[idx])
            break
        else:
            return False

This was my try.

Any help is extremely appreciated.

You will need to go breadth first, not depth. You will need to see that all elements are either lists or ints before you check any of the lists present. — quamrana
– quamrana, Commented Dec 1, 2020 at 12:09

quamrana · Accepted Answer · 2020-12-01 12:21:12Z

3

Its possible to write code which mirrors the requirements:

Return True if all items in a list are ints.

Return True if all items in a list are lists and those sublists are also compliant.

Else return False

def intSuperListe(list_to_check):
    areInts = all(isinstance(item, int) for item in list_to_check)
    if areInts:
        return True

    areLists = all(isinstance(item, list) for item in list_to_check)
    if areLists:
        return all(intSuperListe(item) for item in list_to_check)

    return False


for item in [[1, 2], [[1, 2, [1]]], [[1], [2], [[3], [1]]]]:
    print(intSuperListe(item), item)

Output:

True [1, 2]
False [[1, 2, [1]]]
True [[1], [2], [[3], [1]]]

answered Dec 1, 2020 at 12:21

quamrana

39.5k13 gold badges57 silver badges77 bronze badges

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

Comments

Jason Yang · Accepted Answer · 2020-12-01 13:01:56Z

1

def intSuperListe(list_to_check):
    if all(map(lambda x:isinstance(x, int), list_to_check)):
        return True
    elif all(map(lambda x:isinstance(x, list), list_to_check)):
        return all(map(intSuperListe, list_to_check))
    return False

>>> a = [1, 2]
>>> b = [[1, 2, [1]]]
>>> c = [[1], [2], [[3], [1]]]
>>> print(intSuperListe(a))
True
>>> print(intSuperListe(b))
False
>>> print(intSuperListe(c))
True

answered Dec 1, 2020 at 13:01

Jason Yang

13.1k2 gold badges11 silver badges29 bronze badges

Comments

FinleyGibson · Accepted Answer · 2020-12-01 12:39:57Z

0

def intSuperListe(lst):

    if all([type(l) == int for l in lst]):
        # if all elements of lst are ints then this is True
        return True
    elif all([type(l) == list for l in lst]):
        # if all elements of lst are lists, recursively check
        # all elements by calling intSuperListe on each
        return all([intSuperListe(l) for l in lst])
    else:
        # If all elements are not list or ints, then return
        # False
        return False


a = [1, 2]
b = [[1, 2, [1]]]
c = [[1], [2], [[3], [1]]]

print(intSuperListe(a))
print(intSuperListe(b))
print(intSuperListe(c))

>>> True
>>> False
>>> True

answered Dec 1, 2020 at 12:39

FinleyGibson

9215 silver badges19 bronze badges

Collectives™ on Stack Overflow

How to properly use recursion on nested lists in python?

Problem statement

My attempt so far

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem statement

My attempt so far

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related