2

I have the following snippet, that beautifully generates binary numbers by altering 0 and 1 in places of "?". But I don't understand how this piece of code works. Especially the line str_list[idx] = "?" . Why is the "?" begin restored in the idx position.

How should one think about this while writing a recursion?

Here is the code

def gen_bin(str_list):
    if "?" not in str_list:
        print "".join(str_list)
        return

    idx = str_list.index("?")
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:])
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:])

    str_list[idx] = "?"


gen_bin(list("1??"))

Any advice on how to write such recursive functions will help me in becoming better.

Thanks for your time.,

Improve this question

2 Answers 2

Reset to default
3

There are two parts to a recursive definition:

  1. The terminating condition. This part is critical, and frequently appears first. The terminating condition is what you test to know if you are "done."

    Generally, a recursive function has some kind of "natural" terminating condition. For example, Fibonacci sequences end when you get back to 1. Factorials end when you get back to 1. List processing ends when you get an empty list. String processing ends with an empty string.

    Whatever it is, any recursive function will fail - generally by looping or recursing infinitely until a stack overflow occurs - unless you have the terminating condition defined correctly, and you check it successfully.

    For this reason, most recursive functions look like this:

    def recursive_func(arg):
    if terminating_condition(arg):
        return simplest_value

    # more code here
    recursive_func(reduced_form(arg))

  2. The recursive relation. Once you have checked (and failed) the test for the terminating condition, you have to invoke the recursive relation. Generally, this means performing a computation involving a slightly lesser form of the same recursive function.

    Examples:

    n! := n * (n-1)!

    fib(n) := fib(n-1) + fib(n-2)

    len(head:tail) := 1 + len(tail)

Real World Example

Let's look at your example:

def gen_bin(str_list):
    if "?" not in str_list:
        print "".join(str_list)
        return

    idx = str_list.index("?")
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:])
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:])

    str_list[idx] = "?"

gen_bin(list("1??"))

It's pretty clear that this functions follows the classic structure. The first paragraph is a test of the terminating condition. In this case, the terminating condition is that there is not a '?' in the string to replace.

The remainder of the function is dedicated to the recursive relation. In this case, that consists of replacing the first occurrence of '?' in the string with either a '0' or a '1' and recursing.

I'll argue that this is not very good code. First of all, the assignment at the end, str_list[idx] = "?", does nothing. I suspect this code was recently modified. It probably edited the str_list in place, setting a '0' and a '1' into str_list[idx] directly instead of using a slice.

More to the point, though, this isn't good code because all it does is print the results. It would be a better function if it returned a list of binary strings, rather than trying to print them.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for the detailed explanation. I see that the line of code is not doing anything. This code makes 2 recursive calls. one with 0 and the other with 1. how do I modify the same function to call both the sub recursive functions in 1 line or single call.
That depends on what you're trying to do. Probably the easiest way would be to enumerate the two: call('0'), call('1')
3

The function gen_bin() simply looks for the first occurrence of ? in an input argument list, with this line:

idx = str_list.index("?")

then just inserts 0 in that place, and runs recursively with that new list as a new argument:

gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:])

and then inserts 1 there and runs recursively again:

gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:])

If there is no ? in the str_list it just prints out the argument.

The line:

str_list[idx] = "?"

is unnecessary and does completely nothing, which You can observe running the following code:

def gen_bin(str_list):
    if "?" not in str_list:
        #print "".join(str_list)
        return

    idx = str_list.index("?")
    gen_bin(str_list[:idx] + ["0"] + str_list[idx+1:])
    gen_bin(str_list[:idx] + ["1"] + str_list[idx+1:])

    print str_list
    str_list[idx] = "?"
    print str_list

gen_bin(list("1??"))

which returns:

['1', '0', '?']
['1', '0', '?']
['1', '1', '?']
['1', '1', '?']
['1', '?', '?']
['1', '?', '?']
Improve this answer

2 Comments

Thanks for explaining it to me. You are right. That line of code isn't doing anything. Now how do I combine the 2 recursive calls (one inserting 0 and the other inserting 1)that we make inside the function into a single recursive call?
I don't understand, why do You want to combine those 2 calls?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.