Week5 - More Recursion and Time Control

Hi Everyone,

This week we handed in our assignment1, which takes three of us a whole weekend to do. We found the recursive functions are the most difficult part. We reviewed many recursive functions from lectures and labs when we're writing our codes. There are three interesting codes which I think mostly improved my programming skills. In this week's post, I am going to share these three recursive functions with you. At the end of this post, I am going to talk about how to control program running time in Python. Thank you for reading :)

Binary Represent:

This is the function that uses recursion to build a program converting numbers into binary numbers, even more surprising, we can do for ternary numbers, quaternary numbers, and even k-nary numbers!

We develop our k-nary numbers by first solving the problem for binary numbers. Here we used the programming skill that we mentioned in Week3's post, solving a big programming problem by solving a simpler case first.

def bin_rep(n: int) -> str:

    """Return binary representation of n in base 2

    n --- non-negative integer

    >>> bin_rep(0) == "0"

    True

    >>> bin_rep(1) == "1"

    True

    >>> bin_rep(5) == "101"

    True

    """

    return bin_rep(n // 2) + bin_rep(n % 2) if n > 1 else str(n)

Note:

# The binary representation of n is the binary representation of

# n // 2 concatenated with the binary representation of n’s last bit

# provided n > 1, otherwise it’s just n as a string

def bin_rep(n: int, k: int) -> str:

    """Return binary representation of n in base 2

    n --- non-negative integer

    >>> bin_rep(0, 10) == "0"

    True

    >>> bin_rep(1, 2) == "1"

    True

    >>> bin_rep(5, 3) == "12"

    True

    """

    return bin_rep(n // k, k) + bin_rep(n % k, k) if n > k - 1 else str(n)

Note: 
# The binary representation of n is the binary representation of
# n // k concatenated with the binary representation of n’s last bit
# provided n > k - 1, otherwise it’s just n as a string

Nested Depth:

The second example is "nested_depth", which is a typical recursion-use function, and there's a small trick that we should be careful of: when we use a built-in method (such as 'max' in this example) applied to a list, we should make the list is not empty. The easy way to control a non-empty is by adding [0] (as highlighted in the code below).

def nested_depth(L):

    """

    Return if L is non-list, or 1 + maximum of depths of elements list L.

    Not defined for infinitely nested lists.

    >>> nested_depth(3)

    0

    >>> nested_depth([1, 2, 3])

    1

    >>> nested_depth([1, [2, 3], 4])

    2

    """

    return (1 + max([nested_depth(x) for x in L] +[0]) if isinstance(L,list) else 0)

 #Note: the [0] is in case we have an empty list

Tower of Hanoi (three stools, seq_of_move):

The last function I am going to talk about is from our Assignment. All the recursive functions we see so far only call themselves once; in this part of Hanoi function, we call the Hanoi function twice within itself. So we learned that the recursive function can happens several times. 

The following code is the sample code provided by Prof. Heap, I am not supposed to post our code here but we use the exactly same strategy.

def move_cheeses(n: int, source: int, intermediate: int, destination: int) -> None:

    """Print moves to get n cheeses from source to destination, possibly using intermediate"""

    if n > 1:

        move_cheeses(n - 1, source, destination, intermediate)

        move_cheeses(1, source, intermediate, destination)

        move_cheeses(n -1, intermediate, source, destination)

    else: # just one cheese --- no recursion required!

        print("Move top cheese from {} to {}".format(source, destination))

Control Program Running Time (with Time module):

We studied too hard to figure this out, even though it's simple haha. If someday you're asked to control your programming running time, there is a built-in model in Python called "time". The thinking here is set the init time first, then the second time, if the time difference is smaller than the one we want, let the program keep running, time2 continuously increase, until (time2 - time1) = time_difference, other codes will run after.

The sample code is as following:

time1 = time.time()

time2 = time.time()

while (time2 - time1) < time_difference:

      time2 = time.time()

#other codes

I am going to talk about scopes and tree class in next week's post. Come back soon~