their nested lists recursion versus queues and stacks it sometimes helps to understand that internallypython implements recursion by pushing information on call stack at each recursive callso it remembers where it must return and continue later in factit' generally possible to implement recursive-style procedures without recursive callsby using an explicit stack or queue of your own to keep track of remaining steps for instancethe following computes the same sums as the prior examplebut uses an explicit list to schedule when it will visit items in the subjectinstead of issuing recursive callsthe item at the front of the list is always the next to be processed and summeddef sumtree( )tot items list(lwhile itemsfront items pop( if not isinstance(frontlist)tot +front elseitems extend(frontreturn tot breadth-firstexplicit queue start with copy of top level fetch/delete front item add numbers directly <=append all in nested list technicallythis code traverses the list in breadth-first fashion by levelsbecause it adds nested listscontents to the end of the listforming first-in-first-out queue to emulate the traversal of the recursive call version more closelywe can change it to perform depth-first traversal simply by adding the content of nested lists to the front of the listforming last-in-first-out stackdef sumtree( )tot items list(lwhile itemsfront items pop( if not isinstance(frontlist)tot +front elseitems[: front return tot depth-firstexplicit stack start with copy of top level fetch/delete front item add numbers directly <=prepend all in nested list for more on the last two examples (and another variant)see file sumtree py in the book' examples it adds items list tracing so you can watch it grow in both schemesand can show numbers as they are visited so you see the search order for instancethe breadth-first and depth-first variants visit items in the same three test lists used for the recursive version in the following ordersrespectively (sums are shown last) :\codesumtree py recursive functions