Lab 4: Recursion and Tree Recursion

Due at 11:59pm on 07/02/2015.

Starter Files

Download lab04.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 with python3 ok --submit. 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, 6, 7, 8, and 9 in lab04.py and submit through OK.
  • Questions 2, 3, 4, and 5 are to show you what some common recursion misconceptions and mistakes are.
  • Questions 10 is extra practice. It can be found in the lab04_extra.py file. It is recommended that you complete this problem on your own time.

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.

Question 1: Skip Add

Write a function skip_add that takes a single argument n and computes the sum of every other integers between 0 and n starting from n. Assume n is non-negative.

def skip_add(n):
    """ Takes a number x and returns x + x-2 + x-4 + x-6 + ... + 0.

    >>> skip_add(5)  # 5 + 3 + 1 + 0
    9
    >>> skip_add(10) # 10 + 8 + 6 + 4 + 2 + 0
    30
    """

    "*** YOUR CODE HERE ***"

    if n <= 0:
        return 0
    return n + skip_add(n - 2)

Use OK to test your code:

python3 ok -q skip_add

Question 2: Common Misconception

Fix the error with the following recursive function.

def count_up(n):
    """Print out all numbers up to and including n in ascending order.

    >>> count_up(5)
    1
    2
    3
    4
    5
    """
    i = 1
    if i == n:
        return
    print(i)
    i += 1
    count_up(n-1)

The variable i resets back to 1 for each function call and will print 1 each time. Try it out!

Question 3: 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)

Consider what happens when we choose an odd number for n. skip_mul(3) will return 3 * skip_mul(1). skip_mul(1) will return 1 * skip_mul(-1). You may see the problem now. Since we are decreasing n by two at a time, we've completed missed our base case of n == 0, and we will end up recursing indefinitely. We need to add another base case to make sure this doesn't happen.

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

Question 4: 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)

The result of the recursive calls is not returned.

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

Question 5: Common Misconception

Fix the error with the following recursive function:

def print_up_to(n):
    """Print every natural number up to n, inclusive.

    >>> print_up_to(5)
    1
    2
    3
    4
    5
    """
    i = 1
    if i > n:
        return
    else:
        print(i)
        i += 1
        print_up_to(n)

The function never reduces toward the base case of i == n.

def print_up_to(n):
    def helper(i):
        print(i)
        if i < n:
            helper(i + 1)
    helper(1)

Note:

  • To keep track of info between recursive calls, we passsed the information as arguments to the function. This also allows us to get by without explicitly assigning a counter.
  • The helper function doesn't have a base case written. The base case is implicit because we have the condition i < n We will stop recursing once i == n and we violate this condition.

Question 6: 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)

# 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

Use OK to test your code:

python3 ok -q gcd

Question 7: Hailstone

For the hailstone function from homework 1, you pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the
    number of elements in the sequence.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """

    "*** YOUR CODE HERE ***"

    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone(n // 2)
    else:
        return 1 + hailstone(3 * n + 1)

Use OK to test your code:

python3 ok -q hailstone

Tree Recursion

A tree recursive function is a recursive function that makes more than one call to itself, resulting in a tree shaped process.

The classic example for tree recursion is fibonacci.

Fibonacci Tree

Question 8: Fibonacci

Write the fibonacci function using tree recursion. The function should take in n and return the nth fibonacci number.

As a reminder, Fibonacci is defined as a function where:

Fibonacci Tree

def fibonacci(n):
    """Return the nth fibonacci number.

    >>> fibonacci(11)
    89
    >>> fibonacci(5)
    5
    >>> fibonacci(0)
    0
    >>> fibonacci(1)
    1
    """

    "*** YOUR CODE HERE ***"

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Use OK to test your code:

python3 ok -q fibonacci

Question 9: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

grid

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """

    "*** YOUR CODE HERE ***"

    if m == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Use OK to test your code:

python3 ok -q paths

Extra Questions

Questions in this section are not required for submission. However, we encourage you to try them out on your own time for extra practice.

Question 10: 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

Write a function interleaved_sum 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.)

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:

python3 ok -q interleaved_sum