converting lists in list to a list only containing integers using recursion

Question

One of the questions I had on an exam was to write a python program only using recursion (no loops were allowed). The goal was to convert a list which contained both integers and lists (which also only contained integers) and make a single list only containing these integers.

Everything works fine in the code below until it encounters a list: after this it just stops. The fix has to be fairly simple but I just can't find it.

a = [1,5,2,[3,4],6]

def list_in_list(l, i = 0):
    if i >= len(l) - 1:
        return [l[i]] if type(l[i]) == int else list_in_list(l[i], i=0)
    elif type(l[i]) == list:
        return list_in_list(l[i],i=0)
    return [l[i]] + list_in_list(l, i+1)
print(list_in_list(a))

I despise problems like this. This isn't the type of problem that should be done with recursion just because.... It just takes up stack for no reason. — Error - Syntactical Remorse, Jul 26 '19 at 14:45
Possible duplicate of https://stackoverflow.com/questions/12472338/flattening-a-list-recursively — StardustGogeta, Jul 26 '19 at 14:49
Possible duplicate of [Flattening a list recursively](https://stackoverflow.com/questions/12472338/flattening-a-list-recursively) — StardustGogeta, Jul 26 '19 at 14:49

Andrej Kesely · Accepted Answer · 2019-07-26T15:08:19.567

2

This works for any level of any level of nested lists:

a = [1,5,2,[3, [4, 7]],6]

def flatten(lst):
    if not lst:
        return []

    first, rest = lst[0], lst[1:]

    if isinstance(first, list):
        return flatten(first) + flatten(rest)
    else:
        return [first] + flatten(rest)


print(flatten(a))

Prints:

[1, 5, 2, 3, 4, 7, 6]

edited Jul 26 '19 at 15:08

answered Jul 26 '19 at 14:48

Andrej Kesely

168,389
15
48
91

1

May just want to add a comment to make sure the OP notices he should use `isinstance` instead of `type`. – Error - Syntactical Remorse Jul 26 '19 at 14:49

Error - Syntactical Remorse · Answer 2 · 2019-07-26T14:57:42.997

The other answer did it without a loop as your question asked but I just wanted to make a few points.

1) Don't using type such as type(a) == str. Use isinstance(a, str). If you want to know why see What are the differences between type() and isinstance()?

2) I made the comment above and I know this is from exam, but this type of problem is inefficient to do with just pure recursion. Recursion is useful for a problem like this (I have done stuff like this a lot with JSON) but using pure recursion without using a loop takes up excessive memory and more time:

a = [1,5,2,[3, [4, 7]],6]

def list_in_list(l):
    result = []
    for element in l:
        if isinstance(element, list):
            result += list_in_list(element)
        else:
            result.append(element)
    return result
print(list_in_list(a)) # [1, 5, 2, 3, 4, 7, 6]

score 0 · Answer 3 · answered Jul 27 '19 at 03:53

Since you specified the [python-3x] tag, let's take advantage of some Python 3 features. Also, let's make the flatten() function have a single point of return instead of three:

example = [[8, 3, [2, 4, 1, [9, [7, 5, 6, [0]]]]]]

def flatten(array):
    if array:
        first, *array = array

        if array:
            array = flatten(array)

        array = ([first] if isinstance(first, int) else flatten(first)) + array

    return array

print(flatten(example))

We also save some recursions by doing an empty list check on the remainder of the list to decide if it's worth recuring.

USAGE

> python3 test.py
[8, 3, 2, 4, 1, 9, 7, 5, 6, 0]
>

converting lists in list to a list only containing integers using recursion

3 Answers3