Python Forum

def sumtree(l):
    tot = 0
    for x in l:
        if not isinstance(x, list):
            tot += x
            print(tot)
        else:
            tot += sumtree(x)
            print('xxx')
    return tot

o = [1, [2, [3, 4], 5], 6, [7, 8]]

I don't understand how this works. It sums the items in the nested nested lists.
I've typed this interactively:
>>> type(o[0])
<class 'int'>
>>> type(o[1])
<class 'list'>
>>> type(o[2])
<class 'int'>
>>> type(o[3])
<class 'list'>

>>> o[1]
[2, [3, 4], 5]
>>> o[0]
1
>>> o[1]
[2, [3, 4], 5]
>>> o[2]
6
>>> o[3]
[7, 8]

if I run it it gives this:

1
2
3
7
xxx
14
xxx
21
7
15
xxx
36
1
3
6
10
10

The for loop seems to step over the first item in each nested list, but why does it do that? It's probably really easy, I've been staring at it for hours. Any help or explanation would be greatly appreciated.

Yes, recursive algorithms are always difficult to understand.
When I have a program of which I do not understand the results, I add print statements to them so I can follow what happens from step to step. Like this:

def sumtree(l):
    tot = 0
    print(f"New instance of sumtree({l})")
    for x in l:
        if not isinstance(x, list):
            tot += x
            # print(tot)
        else:
            tot += sumtree(x)
            # print('xxx')
    print(f"End of sumtree({l}), returning: {tot}")
    return tot


o = [1, [2, [3, 4], 5], 6, [7, 8]]
print(sumtree(o))

Output:
New instance of sumtree([1, [2, [3, 4], 5], 6, [7, 8]])
New instance of sumtree([2, [3, 4], 5])
New instance of sumtree([3, 4])
End of sumtree([3, 4]), returning: 7
End of sumtree([2, [3, 4], 5]), returning: 14
New instance of sumtree([7, 8])
End of sumtree([7, 8]), returning: 15
End of sumtree([1, [2, [3, 4], 5], 6, [7, 8]]), returning: 36
36

Does this make clear what happens?

(Nov-22-2020, 01:33 PM)ibreeden Wrote: [ -> ]Does this make clear what happens?

Thanks for your quick reply. It helps, but I still don't get it.

I'm under the impression that when l[1] (second item, [2, [3,4], 5])passes through the if not instance expression it should return False. Shouldn't it then proceed to else?

tnx in advance

(Nov-22-2020, 06:34 PM)tames Wrote: [ -> ]\I'm under the impression that when l[1] (second item, [2, [3,4], 5])passes through the if not instance expression it should return False. Shouldn't it then proceed to else?

It does. But when it goes there it runs another sumtree (which might do a lot of thing) before printing out the "xxx".

If I run it with just the list [[3, 4]], you get:

Output:
x [3, 4] list? True
3
7
xxx

The [3,7] is found and goes into the "else" branch. In that branch, it calls sumtree() again, which prints out the 3 and the 4. The recursive sumtree exits and the xxx is printed. Printing something before the sumtree is run would make it more explicit:

def sumtree(l):
    tot = 0
    for x in l:
        #print(f"x {x} list? {isinstance(x, list)}")
        if not isinstance(x, list):
            tot += x
            print(tot)
        else:
            print(f" running recursive sumtree for {x}")
            tot += sumtree(x)
            print(f" exited recusive sumtree for {x}")
            print('xxx')
    return tot

o = [1, [2, [3, 4], 5], 6, [7, 8]]

Output:
1
 running recursive sumtree for [2, [3, 4], 5]
2
 running recursive sumtree for [3, 4]
3
7
 exited recusive sumtree for [3, 4]
xxx
14
 exited recusive sumtree for [2, [3, 4], 5]
xxx
21
 running recursive sumtree for [7, 8]
7
15
 exited recusive sumtree for [7, 8]
xxx

(Nov-22-2020, 06:34 PM)tames Wrote: [ -> ]It helps, but I still don't get it.

As I said, just use your imagination and add print statements so you can follow exactly what is happening.
Just to give an idea I added indentation. Each invocation of the function has it's own indentation.

indent = 0

def sumtree(l):
    global indent
    indent += 4
    id = indent * "_"
    tot = 0
    print(id + f"New invocation of sumtree({l})")
    for x in l:
        if not isinstance(x, list):
            print(id + f"Adding {tot} + {x} = {tot+x}")
            tot += x
        else:
            subtot = sumtree(x)
            print(id + f"Adding {tot} + {subtot} = {tot+subtot}")
            tot += subtot
    print(id + f"End of sumtree({l}), returning: {tot}")
    indent -= 4
    return tot


o = [1, [2, [3, 4], 5], 6, [7, 8]]
print(sumtree(o))

Output:
____New invocation of sumtree([1, [2, [3, 4], 5], 6, [7, 8]])
____Adding 0 + 1 = 1
________New invocation of sumtree([2, [3, 4], 5])
________Adding 0 + 2 = 2
____________New invocation of sumtree([3, 4])
____________Adding 0 + 3 = 3
____________Adding 3 + 4 = 7
____________End of sumtree([3, 4]), returning: 7
________Adding 2 + 7 = 9
________Adding 9 + 5 = 14
________End of sumtree([2, [3, 4], 5]), returning: 14
____Adding 1 + 14 = 15
____Adding 15 + 6 = 21
________New invocation of sumtree([7, 8])
________Adding 0 + 7 = 7
________Adding 7 + 8 = 15
________End of sumtree([7, 8]), returning: 15
____Adding 21 + 15 = 36
____End of sumtree([1, [2, [3, 4], 5], 6, [7, 8]]), returning: 36
36

This is briljant, thank you so much. It's amazing how much a piece of code you don't understand can occupy your mind.

I added another print statement at the beginning of the else loop:

print('---entering else---')

and now I see what you mean.

My mind is at ease (for now :-) ). Thanks again. Someday I will get the hang of this coding stuff.