CODEWITHSUNDEEP
pythonpython-3.xrecursion
Zy Taga
Zy Taga

Reputation: 89

Traverse a nested list

I'm trying to use recursion to traverse a list and append all its non-list elements and the elemnents of the sublists to a unique list.

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            refr(item)
        else:
            loo.append(item)
    return loo

print(refr([1, ['no', 'ok'], 'dang', 0]))

When I define loo as a local variable it only contains the elements of the input list that are not representing a list.

# output

[1, 'dang', 0]

But when defined it as globlal the output is correct

# output

[1, 'no', 'ok', 'dang', 0]

Why so?

Upvotes: 0

Views: 183

Answers (3)

I'mahdi
I'mahdi

Reputation: 24049

use extend(item) from document:

list.extend(iterable) Extend the list by appending all the items from the iterable. Equivalent to a[len(a):] = iterable.

try this:

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            loo.extend(refr(item))
            # OR
            # loo += refr(item)
        else:
            loo.append(item)
    return loo

print(refr([1, ['no', 'ok'], 'dang', 0]))

output:

[1, 'no', 'ok', 'dang', 0]

for this input get correct output:

print(refr([1, [['no', 'ok'], ['dang', 0]]]))
# [1, 'no', 'ok', 'dang', 0]

Upvotes: 2

user2390182
user2390182

Reputation: 73460

You are not using the return value of your recursive call:

def refr(a_list):
    loo = []
    for item in a_list:
        if isinstance(item, list):
            loo += refr(item)
        else:
            loo.append(item)
    return loo

Or, using a generator function, which is often sufficient, allows short-circuiting and can easily be turned into a list:

def refr(a_list):
    for item in a_list:
        if isinstance(item, list):
            yield from refr(item)
        else:
            yield item

From here, it is not far to a one-liner, using itertools.chain:

from itertools import chain

def refr(a_list):
    return chain.from_iterable(refr(x) if isinstance(x, list) else [x] for x in a_list)

[*refr([1, ['no', 'ok', [1, 2, [3]]], 'dang', 0])]
# [1, 'no', 'ok', 1, 2, 3, 'dang', 0]

Upvotes: 3

Jan Wilamowski
Jan Wilamowski

Reputation: 3599

Because the scope of the local (!) loo variable is the refr function for that specific invocation. That means when you call refr recursively, it will create a new stack frame with another empty list that has nothing to do with the first one (it just happens to have the same name). One way to solve this is to add an accumulator parameter to your function call that serves as the combined state:

def refr(a_list, acc=None):
    if acc is None:
        acc = []
    for item in a_list:
        if isinstance(item, list):
            refr(item, acc)
        else:
            acc.append(item)
    return acc

refr([1, ['no', 'ok'], 'dang', 0])

gives

[1, 'no', 'ok', 'dang', 0]

Upvotes: 1

Related Questions