Lab 1: Environment Diagrams and Recursion

Due at 11:59pm on 09/18/2016.

Starter Files

Download lab01.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab using ok. You may submit more than once before the deadline; only the final submission will be graded.

• To receive credit for this lab, you must complete questions 1, 2, 3, 4, 7. If you complete the challenge problem, you can skip one of the required questions and still receive full credit.

Environment Diagrams

An environment diagram keeps track of all the variables that have been defined and the values they are bound to.

x = 3

def square(x):
    return x ** 2

square(2)

When Python executes assignment statements (like x = 3), it records the variable name and the value:

1. Evaluate the expression on the right side of the = sign.
2. Write the variable name and the expression's value in the current frame.

When Python executes def statements (like def square(x):), it records the function name and binds it to a function object:

1. Write the function name (square) in the frame and point it to a function object (func square(x) [parent=Global]). The [parent=Global] denotes the frame in which the function was defined.

When Python executes a call expression (like square(2)), it creates a new frame to keep track of local variables.

1. Draw a new frame. Label it with

   • a unique index (f1, f2, f3 and so on)

   • the intrinsic name of the function (square), which is the name of the function object itself

     • For example, if the function is func square(x) [parent=Global], the intrinsic name is square
   • the parent frame ([parent=Global])
2. Bind the formal parameters to the arguments passed in (e.g. bind x to 3).
3. Evaluate the body of the function.

If a function does not have a return value, it implicitly returns None. Thus, the "Return value" box should contain None.

Since we do not know how built-in functions like add(...) or min(...) or print(...) are implemented, we do not draw a new frame when we call built-in functions.

Recursion

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have three important components:

1. Base case(s), the simplest possible form of the problem you're trying to solve.
2. Consider a recursive call on a smaller argument.
3. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.

Let's look at the canonical example, factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

We know by its definition that 0! is 1. So we choose n = 0 as our base case. The recursive step also follows from the definition of factorial, i.e. n! = n * (n-1)!.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Consider how you can solve the current problem using the solution to a simpler version of the problem. Remember to trust the recursion: assume that your solution to the simpler problem works correctly without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recursive solutions fail).
• It may help to write the iterative version first.

Required Questions

Question 1: Sine

Now we're going to approximate the sine trigonemetric function using 2 useful facts. One is that sin(x) is approximately equal to x as x gets small (for this question, below 0.0001). The other fact is the trigonometric identity

Using these two facts, write a function sine that returns the sine of a value in radians.

def sine(x):
    """Returns the value of sine(x), where x is a value in radians.

    >>> from math import pi
    >>> sine(pi) #Notice how the value is very small but not quite 0.
    -1.482085565385205e-09 
    >>> sine(pi/2)
    1.0
    >>> sine((7 * pi)/2)
    -1.0
    >>> sine(1.5)
    0.9974949867067586
    """
    "*** YOUR CODE HERE ***"
    if abs(x) < 0.0001:
        return x
    return 3 * sine(x / 3) - 4 * pow(sine(x / 3), 3)

Use OK to test your code:

python ok -q sine --local

Question 2: G function

A mathematical function G on positive integers is defined by two cases:

G(n) = n,                                       if n <= 3
G(n) = G(n - 1) + 2 * G(n - 2) + 3 * G(n - 3),  if n > 3

Write a recursive function g that computes G(n).

def g(n):
    """Return the value of G(n), computed recursively.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    "*** YOUR CODE HERE ***"
    if n in (1, 2, 3):
        return n
    return g(n-1) + 2*g(n-2) + 3*g(n-3)
# Iterative solution, if you're curious
def g_iter(n):
    """Return the value of G(n), computed iteratively.

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    """
    if n == 1 or n == 2 or n == 3:
        return n
    a, b, c = 1, 2, 3
    while n > 3:
        a, b, c = b, c, c + 2*b + 3*a
        n = n - 1
    return c

Use OK to test your code:

python ok -q g --local

Question 3: Hailstone

Complete this question first using iteration (while or for loop), then using recursion.

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle:

1. Pick a positive integer n as the start.
2. If n is even, divide it by 2.
3. If n is odd, multiply it by 3 and add 1.
4. Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried — nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

The sequence of values of n is often called a Hailstone sequence, because hailstones also travel up and down in the atmosphere before falling to earth. Write two different versions (iterative and recursive) of a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

Use OK to test your code:

python ok -q hailstone_iterative --local
python ok -q hailstone_recursive --local

Question 4: Remove from sequence

Complete the recursive function remove which removes the first element in a sequence that is equal to a specified value.

def first(s):
    """Return the first element in a sequence."""
    return s[0]

def rest(s):
    """Return all elements in a sequence after the first"""
    return s[1:]

def remove(x, s):
    """Remove first element equal to x from sequence s.

    >>> remove(1,[])
    []
    >>> remove(1,[1])
    []
    >>> remove(1,[1,1])
    [1]
    >>> remove(1,[2,1])
    [2]
    >>> remove(1,[3,1,2])
    [3, 2]
    >>> remove(1,[3,1,2,1])
    [3, 2, 1]
    >>> remove(5, [3, 5, 2, 5, 11])
    [3, 2, 5, 11]
    """
    "*** YOUR CODE HERE ***"
    if not s:
        return []
    elif first(s) == x:
        return rest(s)
    else:
        return [first(s)] + remove(x, rest(s))

Illustrated here is a more complete doctest that shows good testing methodology. It is a little cumbersome as documentation, but you'll want to think about it for your projects. Test every condition that might come up. Then you won't be surprised when it does.

Use OK to test your code:

python ok -q remove --local

Question 5: Common Misconception

Fix the error with the following recursive function.

def factorial(n):
    """Return n * (n - 1) * (n - 2) * ... * 1.

    >>> factorial(5)
    120
    """
    if n == 0:
        return 1
    else:
        n * factorial(n-1)

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Question 6: Common Misconception

Fix the error with this recursive function.

def skip_mul(n):
    """Return the product of n * (n - 2) * (n - 4) * ...

    >>> skip_mul(5) # 5 * 3 * 1
    15
    >>> skip_mul(8) # 8 * 6 * 4 * 2  * 0
    0
    """
    if n == 0:
        return 0
    else:
        return n * skip_mul(n - 2)

def skip_mul(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return n * skip_mul(n - 2)

Question 7: GCD

The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:

• the smaller value if it evenly divides the larger value, OR
• the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if a is greater than b and a is not divisible by b, then

gcd(a, b) == gcd(b, a % b)

Write the gcd function recursively using Euclid's algorithm.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"
    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

Use OK to test your code:

python ok -q gcd --local

This is an example of the elegance that recursive solutions permit. Here for comparison is an iterative solution.

# Iterative solution, if you're curious
def gcd_iter(a, b):
    """Returns the greatest common divisor of a and b, using iteration.

    >>> gcd_iter(34, 19)
    1
    >>> gcd_iter(39, 91)
    13
    >>> gcd_iter(20, 30)
    10
    >>> gcd_iter(40, 40)
    40
    """
    if a < b:
        return gcd_iter(b, a)
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

Challenge Question

Questions in this section are not required for submission. However, if you do a challenge question, you can skip another question on the lab without losing points.

Question 8: Interleaved Sum

Recall that the summation function computes the sum of a sequence of terms from 1 to n:

def summation(n, term):
    """Return the sum of the first n terms of a sequence.

    >>> summation(5, lambda x: pow(x, 3))
    225
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total

Two things to note here. First, the funny lambda that you haven't seen yet is a slick way to create an anonymous function. We'll see it later. Here we are using it just for testing. It is simpler than something like:

>>> def cube(x):
...    return pow(x,3)
>>> summation(5, cube)
225

Secondly, this is using a while loop to do what we would do in a more structured fashion with a for loop.

def summation(n,term):
    total = 0
    for k in range(1,n+1):
        total = total + term(k)
    return total

At this point, you should be able to read (or write) either one. For a given question, you can usually use either type of loop. Depending on the context, one type of loop may be more clear than the other. Another way to write such functions is using recursion.

Write a function interleaved_sum using recursion that similarly computes the sum of a sequence of terms from 1 to n, but uses different function to compute the terms for odd and even numbers. Do so without using any loops or testing in any way if a number is odd or even. (You may test if a number is equal to 0, 1, or n.)

Hint: Use a recursive helper function!

def interleaved_sum(n, odd_term, even_term):
    """Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
    to n.

    >>> # 1 + 2^2 + 3 + 4^2 + 5
    ... interleaved_sum(5, lambda x: x, lambda x: x*x)
    29
    """
    "*** YOUR CODE HERE ***"
    return interleaved_helper(n, odd_term, even_term, 1)

def interleaved_helper(n, term0, term1, k):
    if k == n:
        return term0(k)
    return term0(k) + interleaved_helper(n, term1, term0, k+1)

# Alternate solution
def interleaved_sum2(n, odd_term, even_term):
    """Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
    to n.

    >>> # 1 + 2^2 + 3 + 4^2 + 5
    ... interleaved_sum2(5, lambda x: x, lambda x: x*x)
    29
    """
    total, term0, term1 = interleaved_helper2(n, odd_term, even_term)
    return total

def interleaved_helper2(n, odd_term, even_term):
    if n == 1:
        return odd_term(1), even_term, odd_term
    else:
        total, term0, term1 = interleaved_helper2(n-1, odd_term,
                                                  even_term)
    return total + term0(n), term1, term0

Use OK to test your code:

python ok -q interleaved_sum --local

Environment Diagram Rules

1. Creating a Function

   • Draw the func <name>(<arg1>, <arg2>, ...)
   • The parent of the function is wherever the function was defined (the frame we're currently in, since we're creating the function).
   • If we used def, make a binding of the name to the value in the current frame.

2. Calling User Defined Functions

   • Evaluate the operator and operands.
   • Create a new frame; the parent is whatever the operator's parent is. Now this is the current frame.
   • Bind the formal parameters to the argument values (the evaluated operands).
   • Evaluate the body of the operator in the context of this new frame.
   • After evaluating the body, go back to the frame that called the function.

3. Assignment

   • Evaluate the expression to the right of the assignment operator (=).

   • If nonlocal, find the frame that has the variable you're looking for, starting in the parent frame and ending just before the global frame (via Lookup rules). Otherwise, use the current frame.

     • Note: If there are multiple frames that have the same variable, pick the frame closest to the current frame.
   • Bind the variable name to the value of the expression in the identified frame. Be sure you override the variable name if it had a previous binding.

4. Lookup

   • Start at the current frame. Is the variable in this frame? If yes, that's the answer.
   • If it isn't, go to the parent frame and repeat 1.
   • If you run out of frames (reach the Global frame and it's not there), complain.

5. Tips

   • You can only bind names to values. No expressions (like 3+4) allowed on environment diagrams!
   • Frames and Functions both have parents.