Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
basic question isinstance
#1
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.
Reply
#2
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?
Reply
#3
(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
Reply
#4
(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
Reply
#5
(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
Reply
#6
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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Basic Coding Question: Exit Program Command? RockBlok 3 504 Nov-19-2023, 06:31 PM
Last Post: deanhystad
  [solved] Basic question on list matchiing paul18fr 7 1,808 May-02-2022, 01:03 PM
Last Post: DeaD_EyE
  Very basic calculator question BoudewijnFunke 4 1,883 Dec-10-2021, 10:39 AM
Last Post: BoudewijnFunke
  Trying to understand how isinstance(values, collections.Iterable) work. quazirfan 7 4,096 Aug-10-2021, 08:10 AM
Last Post: snippsat
  basic question about tuples and immutability sudonym3 6 2,828 Oct-18-2020, 05:11 PM
Last Post: sudonym3
  Help with isinstance command (very simple code) Laplace12 2 1,966 Jul-30-2020, 05:26 AM
Last Post: Laplace12
  isinstance() always return true for object type check Yoki91 2 2,503 Jul-22-2020, 06:52 PM
Last Post: Yoki91
  Basic Pyhton for Rhino 6 question about variables SaeedSH 1 2,107 Jan-28-2020, 04:33 AM
Last Post: Larz60+
  Basic Beginner question NHeav 4 2,708 Sep-13-2019, 11:43 AM
Last Post: NHeav
  Basic coding question with Python Than999 3 3,058 Jul-17-2019, 04:36 PM
Last Post: jefsummers

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020