Recursive function going infinite and I can't see why.

[=?ISO-8859-1?Q?Gregory_Pi=F1ero?=]

Hi,

Would anyone be able to tell me why my function below is getting stuck
in infinite recusion?
Maybe I'm just tired and missing something obvious?

def replace_within_node(node,oldnode,newnode):
if node is oldnode:
return newnode
else:
for varname,value in node.__dict__.items():
node.__dict__[varname]=replace_within_node(value,oldnode,newnode)
return node

At the end of this email I pasted the whole text of the sample code in
case it would help to see it in context or maybe step through it?

--
Gregory Piñero
Chief Innovation Officer
Blended Technologies
(www.blendedtechnologies.com)


#This is the code that's causing my problem:
#----------------------------------------------------------------------

import random
import sys

class Test_Class:
pass
class Node:
def __init__(self):
self.arg0=0
self.arg1=0
self.arg2=0
self.arg3=0

def snip(node):
prob_of_returning_this_node=.4
if random.random()<=prob_of_returning_this_node:
return node
else:
if hasattr(node,'__dict__') and len(node.__dict__)>0:
return snip(random.choice(node.__dict__.values()))
else:
return node

def replace_within_node(node,oldnode,newnode):
if node is oldnode:
return newnode
else:
if hasattr(node,'__dict__'):
for varname,value in node.__dict__.items():

node.__dict__[varname]=replace_within_node(value,oldnode,newnode)
return node

def generate_random_program(currdepth,mindepth=2,maxdepth=4):
node=Node()
if currdepth==maxdepth:
return node
else:
node=Node()
for varname,value in node.__dict__.items():
node.__dict__[varname]=generate_random_program(currdepth+1,mindepth,maxdepth)
return node

def breed(father,mother):
#want to take subtree from each input parameter and swap them.
snip_from_mother=snip(mother.program)
snip_from_father=snip(father.program)
program_for_father=replace_within_node(father.program,snip_from_father,snip_from_mother)
program_for_mother=replace_within_node(mother.program,snip_from_mother,snip_from_father)
return program_for_father,program_for_mother

if __name__=='__main__':
dragons=[Test_Class() for i in range(10)]
for dragon in dragons:
dragon.program=generate_random_program(0)
for i in range(100):
breed(dragons[0],dragons[1])

 

[Steven D'Aprano]

Hi,

Would anyone be able to tell me why my function below is getting stuck
in infinite recusion?
Maybe I'm just tired and missing something obvious?

Your code is quite confusing, especially since there is very little
documentation. But I'll make a few comments:

#This is the code that's causing my problem:
#----------------------------------------------------------------------

import random
import sys

class Test_Class:
pass
class Node:
def __init__(self):
self.arg0=0
self.arg1=0
self.arg2=0
self.arg3=0

You appear to be iterating over these attributes. Hint: as soon as you
have more than two pieces of data with names like foo0, foo1, foo2...
you probably want something like this:

def __init__(self):
self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees

You are iterating over everything in __dict__ which is probably not what
you want. Your code has serious side-effects, because you are iterating
over ALL instance attributes, even the ones which are not nodes.

for varname,value in node.__dict__.items():
node.__dict__[varname] = value
# this touches all instance attributes

This is safer:

for index, value in enumerate(node.trees):
node.trees[index] = value
# this only touches what you want

Now people (and you!) can subclass your Node class without breaking it.

def snip(node):
prob_of_returning_this_node=.4
if random.random()<=prob_of_returning_this_node:
return node
else:
if hasattr(node,'__dict__') and len(node.__dict__)>0:
return snip(random.choice(node.__dict__.values()))
else:
return node

This becomes:

def snip(node):
prob_of_returning_this_node = 0.4
if random.random() <= prob_of_returning_this_node:
return node
else:
return snip(random.choice(node.trees))

def replace_within_node(node,oldnode,newnode):
if node is oldnode:
return newnode
else:
if hasattr(node,'__dict__'):
for varname,value in node.__dict__.items():
node.__dict__[varname]=replace_within_node(value,oldnode,newnode)
return node

becomes:

def replace_within_node(node, oldnode, newnode):
if node is oldnode:
return newnode
else:
for indx, nd in node.trees:
node.trees[indx] = replace_within_node(nd, oldnode, newnode)
return node

This is quite a complex function. It seems to me, and perhaps I'm wrong,
you are walking the nodes and ... doing what? When you call this function,
what are the initial arguments you give it? In other words, what are
oldnode and newnode, and where do they get set?


In another post, you wrote:

"By the way, all I'm trying to do here is take two trees, randomly find
a sub-tree of each and swap the sub-trees. So if anyone has a simple
method for doing that I'm certainly open to that too."

How about something like this?

random.shuffle(node.trees)

That does more than you ask, but maybe it is useful to you. If you only
want to swap two, maybe something like this:

a, b = random.randint(0,3), random.randint(0,3)
node.trees[a], node.trees = node.trees, node.trees[a]


I think what you really need to do here is spend some time building a
general tree class, before getting bogged down in the mechanics of your
application. For example, it would be really useful to print your Node,
and all its subtrees, so you can actually confirm that it contains what
you think it contains.

Why is this important? Because if your tree of nodes contains a loop, such
that node 1 has a subtree with node 2 that has a subtree with node 3 that
has a subtree with node 1 again, most recursive algorithms will never
halt, just keep cycling through the tree forever. Could that be your
problem? There is no way for us to tell from the information we've got.

 

[=?ISO-8859-1?Q?Gregory_Pi=F1ero?=]

Thanks for the advice guys. See below.

class Node:
def __init__(self):
self.arg0=0
self.arg1=0
self.arg2=0
self.arg3=0

You appear to be iterating over these attributes. Hint: as soon as you
have more than two pieces of data with names like foo0, foo1, foo2...
you probably want something like this:

def __init__(self):
self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees

I'll try this.

This is quite a complex function. It seems to me, and perhaps I'm wrong,
you are walking the nodes and ... doing what? When you call this function,
what are the initial arguments you give it? In other words, what are
oldnode and newnode, and where do they get set?

I posted the whole code, so that should be in there.

In another post, you wrote:

"By the way, all I'm trying to do here is take two trees, randomly find
a sub-tree of each and swap the sub-trees. So if anyone has a simple
method for doing that I'm certainly open to that too."

How about something like this?

random.shuffle(node.trees)

That does more than you ask, but maybe it is useful to you. If you only
want to swap two, maybe something like this:

a, b = random.randint(0,3), random.randint(0,3)
node.trees[a], node.trees = node.trees, node.trees[a]

That's not quite what I want. I want to walk down each tree and get a
random subtree at a random depth.

I think what you really need to do here is spend some time building a
general tree class, before getting bogged down in the mechanics of your
application. For example, it would be really useful to print your Node,
and all its subtrees, so you can actually confirm that it contains what
you think it contains.

I had a print method for the tree, but that was making an infinite
recursion too!

Why is this important? Because if your tree of nodes contains a loop, such
that node 1 has a subtree with node 2 that has a subtree with node 3 that
has a subtree with node 1 again, most recursive algorithms will never
halt, just keep cycling through the tree forever. Could that be your
problem? There is no way for us to tell from the information we've got.

This sounds like what must be happening. I don't know how else it
could get caught up in an infinite recursion. The problem is, I don't
really know how to tell either ;-0

I guess I need to rethink this whole algorithm. Maybe flatten the
trees somehow and then do the swap? I'll let you guys know what I
come up with.

 

[Scott David Daniels]

.... I want to walk down each tree and get a random subtree at a random depth.

Can you quantify that randomness? Should it be uniform at each level?
Thinking about this may be fruitful. I don't yet know whether you need
to see all leaves before you know which subtree to choose.

Because I am a clueless American, so I don't know if Piñero is a common
name or not. Are you perhaps related to the playwright?

--Scott David Daniels
(e-mail address removed)

 

[=?ISO-8859-1?Q?Gregory_Pi=F1ero?=]

Ok, I finally got it working! See below

class Node:
def __init__(self):
self.arg0=0
self.arg1=0
self.arg2=0
self.arg3=0

You appear to be iterating over these attributes. Hint: as soon as you
have more than two pieces of data with names like foo0, foo1, foo2...
you probably want something like this:

def __init__(self):
self.trees = [0, 0, 0, 0] # they aren't args, they are sub-trees

You are iterating over everything in __dict__ which is probably not what
you want. Your code has serious side-effects, because you are iterating
over ALL instance attributes, even the ones which are not nodes.

for varname,value in node.__dict__.items():
node.__dict__[varname] = value
# this touches all instance attributes

This is safer:

for index, value in enumerate(node.trees):
node.trees[index] = value
# this only touches what you want

Yep, this is what fixed it. Thanks Steve. I turns out that there is
a lot of other stuff in __dict__ that was messing me up and causing
the infinite recursion.

Terry was also kind of right in that I was never hitting my base case,
since I was getting stuck on a var in __dict__ and recursing forever
before I ever got to the base case.

-Greg