Return a set from a recursive function

There are two options here: top-down accumulation, or bottom-up.

If you do it bottom-up, you can do it without needing to mutate anything. This does make it harder (and, sometimes, impossible) to write your recursion as tail-calls, but that's fine because (a) Python doesn't eliminate tail calls anyway, and (b) even if it did, your algorithm wouldn't benefit because it makes multiple calls. So, I'll show that way first:

def gen_strings(max_length, state = "A", str = ""):
    if len(str) > max_length:
        return set()
    if state == "A":
        return (gen_strings(max_length, "B", str + "0") |
                gen_strings(max_length, "C", str + "1"))

    elif state == "B":
        return gen_strings(max_length, "D", str + "1")

    elif state == "C":
        return gen_strings(max_length, "D", str + "0")

    elif state == "D":
        return ({str} |
                gen_strings(max_length, "A", str + "0")
                gen_strings(max_length, "A", str + "1"))

To do it top-down, just pass result along the same way you pass state and str down:

def gen_strings(max_length, state="A", str="", result=None):
    if len(str) > max_length:
        return
    if state == "A":
        gen_strings(max_length, "B", str + "0", result)
        gen_strings(max_length, "C", str + "1", result)
    # etc.

The problem is that this doesn't return the result, it takes it as a parameter—you have to pass in an empty set at the top level, like this:

result = set()
gen_strings(max_length, result=result)

But you can always wrap that up. Rename gen_strings to gen_strings_r, then write this:

def gen_strings(max_length, state="A", str=""):
    result = set()
    gen_strings_r(max_length, state, str, result)
    return result

Or you can combine the two, pass a value down to be used to build a value to return back upward. This gives you the benefits of bottom-up (avoiding mutation) and top-down (allowing tail calls), which makes it a very common idiom in functional languages, especially pure functional languages. But it has no advantage over plain bottom-up in this case, and it requires even bigger changes to your code, so I won't bother writing it.