Recursive Algorithm getting stuck (because of Python Limits?)

Mike C. Fletcher mcfletch at
Mon Apr 28 16:52:26 CEST 2003

You're creating close to a million objects in that tree for depth=8, 
that takes >233MB on my machine and 98s.  I'd guess your machine is just 
going into swapping fits or the like when it starts running out of 
memory.  By the way, doing this can get you down to 81MB and 46s for the 
same depth under Python 2.2.2:

class Node(object):
    __slots__ = ('childNodes',)

Good luck,

Marc Floessel wrote:

>I am trying to execute a simple Tree Building algorithm.
>nTreeBreadth = 7
>nTreeDepth = 7
>class Node:
>    def __init__(self):
>        self.childNodes = []
># Create a recursive Sub-Tree with <nChildren> until we reach the
>final <nDepth>
>def CreateSubTree (oRoot, nChildren, nDepth):
>    for i in range(nChildren):
>        oNewNode = Node()
>        oRoot.childNodes.append(oNewNode)
>        if (nDepth > 1):
>            CreateSubTree (oNewNode, nChildren, (nDepth-1))
>oRoot = Node() # Create the Root Node
>CreateSubTree (oRoot, nTreeBreadth, nTreeDepth-1)
>This works. However increasing the Depth or Breadth to 8 seems to
>break Python. Python rises to about 100 MB memory consumption (as
>indicated by the Windows Task Manager) and then seems to drop and rise
>randomly. The algorithm never finishes. Am I breaking the stack? I
>tried executing the code (with a Depth of 8) in Stackless Python, but
>it didn't finish either, so it doesn't appear to be the stack. Are
>there any other hard limits?

  Mike C. Fletcher
  Designer, VR Plumber, Coder

More information about the Python-list mailing list