Declaring empty variables at the beginning of a recursive function

Question

I've read that you should never test for the existence of a variable; if your program has to check whether a variable exists, you don't "know your variables" and it is a design error. However, I have a recursive function that adds values to a dictionary and a list during each call to the function. In order to avoid declaring global variables, I am trying to make the variables local to the function. But in order to do that, I have to declare myList and myDict as [] and {} in the beginning of the function. Of course, that erases the changes I made to the dict and list in the previous recursive calls, which I don't want. I thought about instating a try ... catch at the beginning, checking for the existence of the variables, and only declaring them as {} and [] if they do not yet exist, but I've read that is bad design. Is there a better way to approach this? I apologize for not attaching any actual code, but I'm still at the beginning stages of planning this function, so there is nothing much to attach.

Answer 1

Creating new local variables will not overwrite the local variables from previous calls. Every time you call the function, you get new local variables. If the function calls itself recursively, each call will get its own local variables. It's difficult to tell from your explanation if this is the answer to your question. You really need to post some code.

Answer 2

There's a python "gotcha" you can make use of here. The default mutable argument (e.g. a dictionary or list) will be mutated in recursion:

def my_function(d={}):
    ...
    #recursion will mutate d

To be used with caution, but it can be useful!

.

A simple example:

def f(a,d=[]):
    d.append(a)
    if a!=2:
        f(2)
    return d

print f(1) # [1,2]

Answer 3

If you really need access to mutable state in your recursive function, you should probably use a class.

In situations like this, using languages that don't support object-oriented programming (OOP), the best approach is often simply to use global variables, possibly contained within their own module to avoid namespace collisions. Global variables are "bad," but sometimes they are the lesser of two (or more) evils. But you're writing code in Python, which provides you with a rich set of OOP constructs. You should use them.

For example, here's a simple recursive Fibonacci function that uses memoization to avoid the O(2^n) complexity of the naive version (note that the leading underscore just means that the name is "private" and shouldn't be used without detailed knowledge of its inner workings):

class _Fib(object):
    def __init__(self):
        self.cache = {0:0, 1:1}
    def __call__(self, n):
        if n not in self.cache:
            self.cache[n] = self(n - 1) + self(n - 2)
        return self.cache[n]

fib = _Fib()

A quick test; note that the second call returns with no perceptible delay:

>>> map(fib, xrange(10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> fib(249)
4880197746793002076754294951020699004973287771475874L

You can see that this "function" (really a callable object) solves the problem you describe by creating the mutable object when it is created. Then it accesses the mutable object via self. There are better ways to write fib than the above, but this is likely to be a good basic design for more complex recursive functions requiring state.

Of course you have many other options. Using a mutable default as mentioned by another answer is quite similar -- but I prefer using a class, because it's much more explicit. You could even store the objects as attributes of the function!

def foo(a, b):
    if base_case(a, b):
        return
    foo.dct[a] = b
    foo.lst.append((a, b))
    foo(a - 1, b - 1)
foo.dct = {}
foo.lst = []

I don't love this construction but it's worth knowing about. Finally, don't completely disregard the most obvious solution:

def foo(a, b, dct, lst):
    if base_case(a, b):
        return
    dct[a] = b
    lst.append((a, b))
    foo(a - 1, b - 1, dct, lst)

Sometimes this is actually the best way! It's certainly simple and explicit.

As a final note, I will observe that you seem to be misunderstanding the nature of function scope. You say

I thought about instating a try ... catch at the beginning, checking for the existence of the variables, and only declaring them as {} and [] if they do not yet exist, but I've read that is bad design.

This isn't bad design. It's broken design -- it just won't work. If your dictionary and your list aren't global, then your try/except will always raise an exception, because at the beginning of a function, no local variables are defined.

This leads me to a final thought. Perhaps you want to create a new dictionary and list every time the function is initially called, and throw them away after the recursion stops. The class-based option above would have to be tweaked in that case; or you could just wrap your recursive function in an outer function that creates them anew every time it is called:

def outer(a, b):
    return _inner_recursive(a, b, {}, [])

def _inner_recursive(a, b, lst, dct):
    #blah blah blah