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

[Steven D'Aprano]

On Sat, 04 Feb 2006 02:18:27 -0500, Gregory Piñero 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?

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[b] = node.trees[b], 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.



-- 
Steven.