CODEWITHSUNDEEP
pythonalgorithmrecursion
PDP
PDP

Reputation: 181

Trying to understand a python recursion function

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.,

Upvotes: 2

Views: 116

Answers (2)

aghast
aghast

Reputation: 15310

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.

Upvotes: 3

Tony Babarino
Tony Babarino

Reputation: 3405

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', '?', '?']

Upvotes: 3

Related Questions