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

[Gregory Piñero]

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.

Thanks again,

-Greg


On 2/4/06, Gregory Piñero <gregpinero at gmail.com> wrote:
> 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])
>


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