Summing nested lists without recursion in python

Question

Given a Python list whose elements are either integers or lists of integers (only we don't know how deep the nesting goes), how can we find the sum of each individual integer within the list?

It's fairly straightforward to find the sum of a list whose nesting only goes one level deep, but what if the nesting goes two, three, or more levels deep?

I know the best approach is recursion, but this is a challenge wherein I have to do it without recursion.

Please help!!

Answer 1

L = [...]
while any(isinstance(i, list) for i in L):
   L = [j for i in L for j in (i if isinstance(i, list) else [i])]

result = sum(L)

Basically you iterate over the outer list and unpack the first level of any inner lists until there are no inner lists left

Answer 2

One mostly-readable (and presumably performant, though I haven't tested it) way to iteratively flatten a list:

from collections import deque

def iterative_flatten(li):
    nested = deque(li)
    res = []
    dq = deque()
    while nested or dq:
        x = dq.pop() if dq else nested.popleft()
        dq.extend(reversed(x)) if isinstance(x, list) else res.append(x)
    return res

Uses deques to avoid nasty O(n**2) behavior from list.pop(0). You can get equivalent results by making a reversed copy and popping from the end, but I find the code a little easier to follow if you just use deques and popleft. On a similar note, it's a line or two less code if you want to mutate the list in-place but way slower (for the same reason; popping from the head of the list is O(n) since every element in the underlying array has to be shifted).

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

iterative_flatten(nested)
Out[116]: [1, 2, 3, 4, 5, 6, 7]

sum(iterative_flatten(nested))
Out[117]: 28

After it's flat, summing is (hopefully) trivial :-)

Answer 3

Here is one solution:

from copy import deepcopy

def recursive_sum(int_list):
    #int_list = deepcopy(int_list)    use this line if don't want to modify original list
    ret = 0
    while len(int_list) > 0:
        elem = int_list.pop(0)
        if type(elem) == int:
            ret += elem
        elif type(elem) == list:
            int_list.extend(elem)
        else:
            raise ValueError
    return ret

testcase = [1,2,3,[4,5,[6,7,8,[9,10]]]]
print recursive_sum(testcase)    # print 55

Basically, it pops first element of input list. If it's Int, add into sum; if it's List, extend to the end of input list