Persistent objects in recursive python functions

Question

I am trying to write a recursive function that needs to store and modify an object (say a set) as it recurses. Should I use a global name inside the function? Another option is to modify or inherit the class of the parameter of the function so that it can keep this persistent object but I don't find it elegant. I could also use a stack if I would forgo the recursion altogether...

Is there a pythonic way of doing this? Could a generator do the trick?

Answer 1

Just pass through your persistent object through the recursive method.

def recursivemethod(obj_to_act_on, persistent_obj=None):

    if persistent_obj == None:
        persistent_obj = set()

    # Act on your object

    return recursivemethod(newobj, persistent_obj)

Answer 2

Pass the set into the recursive method as an argument, then modify it there before passing it to the next step. Complex objects are passed by reference.

Answer 3

Objects are passed by reference. If you're only modifying an object, you can do that from within a recursive function and the change will be globally visible.

If you need to assign a variable inside a recursive function and see it after the function returns, then you can't just assign a local variable with =. What you can do is update a field of another object.

class Accumulator: pass

def foo():
    # Create accumulator
    acc = Accumulator()
    acc.value = 0

    # Define and call a recursive function that modifies accumulator
    def bar(n):
        if (n > 0): bar(n-1)
        acc.value = acc.value + 1
    bar(5)

    # Get accumulator
    return acc.value

Answer 4

If it's a container (not an immutable data type), you can pass the object through:

import random

def foo(bar=None, i=10):
    if bar is None:
        bar = set()
    if i == 0:
        return bar
    bar |= set(random.randint(1, 1000) for i in xrange(10))
    return foo(bar, i - 1)

random_numbers_set = foo()

(Don't ask me what that's meant to do... I was just typing random things :P)

Answer 5

If the object you pass is mutable then changes to it in deeper recursions will be seen in earlier recursions.

Answer 6

1. Use a variable global to the function.

2. Pass the object around as an accumulator:

   def recurse(foo, acc=None):
       acc = {}
       recurse(acc)