Lab 13 - Recursion

Due by 11:59pm on 2023-07-25.

Starter Files

Download lab13.zip. Inside the archive, you will find starter files for the questions in this lab.

Topics

Recursion

A recursive function is a function that calls itself.

Consider the definition of a factorial assuming $ n \ge 1 $:

$$ \begin{aligned} &n! \coloneqq n (n - 1) (n - 2) (n - 3) \cdots 1 \\ &1! = 1 \\ &2! = 2 \cdot 1 \\ &3! = 3 \cdot 2 \cdot 1 \\ &4! = 4 \cdot 3 \cdot 2 \cdot 1 \end{aligned} $$

Here is a recursive function that represents this definition:

def factorial(n):
    """Return the factorial of N, a positive integer."""
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Inside of the body of factorial, we're able to call factorial itself, since the function body is not evaluated until the function is called.

When n is 1, we directly return the factorial of 1, which is 1. This is known as a base case which is the case where we can return from the function without recursing (i.e. calling factorial) and then returning. The base case prevents factorial from recursing infinitely, because it's forced to stop/return.

Since we know that our base case factorial(1) will return, we can compute factorial(2) in terms of factorial(1), then factorial(3) in terms of factorial(2), and so on.

factorial(2)
        2 * factorial(1)
                1

factorial(3)
        3 * factorial(2)
                2 * factorial(1)
                        1

We can do this because recursive calls simplify problems incrementally. In the function factorial the problem is incremented by changing n with n - 1.

3 Steps

There are three main steps in a recursive definition:

Base case. The base case is the simplest function input, or the stopping condition for the recursion. In our example, factorial(1) is our base case for the factorial function.

Note: Some problems may have multiple base cases, so you may need to check a couple conditions before you write the recursive call.
Recursive call The recursive call is where we call the original function inside itself.

Recursive problems are solved incrementally. They rely on small pieces building on each other. These pieces are actually the same pattern over and over again. The recursive call is the pattern that will be repeated.

In our example, factorial(n) you multiply n * n-1 * n-2 * n-3 * ... * 1. The pattern here is the n-1, making factorial(n-1) the recursive call.

You can think of recursion as a "divide and conquer" strategy. Suppose you have a bookshelf that fell over and you're in charge of cleaning up the books. The way you put 1 book away is to pick up a book then place it on the book shelf. You can clean up the whole pile of books by doing those 2 steps for every remaining book.

Here we've divided our problem of cleaning up a pile of books into a series of small problems: picking up 1 book at a time.
Solve the original problem. To figure out the original problem we assume that the recursive call we make will give us the expected result once it finishes running.

We act on this assumption by returning the recursive call at the end

We call this idea the "recursive leap of faith".

Now figure out what the result of our original problem should be, which is what we want to return from our current function call.

In our example, we can compute factorial(n) by multiplying the result of our smaller problem factorial(n-1) (which represents (n-1)!) by n (the reasoning being that n! = n * (n-1)!).

Required Questions

Q1: Warm Up: Recursive Multiplication

These exercises are meant to help refresh your memory of the topics covered in lecture.

Write a function that takes two numbers m and n and returns their product. Assume m and n are positive integers. Use recursion, not mul or *.

Hint: $5 * 3 = 5 + (5 \cdot 2) = 5 + 5 + (5 \cdot 1)$.

For the base case, what is the simplest possible input for multiply?
For the recursive case, what does calling multiply(m - 1, n) do? What does calling multiply(m, n - 1) do? What will the base case look like for each?

def multiply(m, n):
    """ Takes two positive integers and returns their product using recursion.
    >>> multiply(5, 3)
    15
    """
    "*** YOUR CODE HERE ***"

Q2: Is Prime

Write a function is_prime that takes a single argument n and returns True if n is a prime number and False otherwise. Assume n > 1. We implemented this in Discussion 1 iteratively, now time to do it recursively!

For this problem we will need a helper function, meaning we will create a 2nd function that will do the recursion with more arguments than the given parameters. This way we can track more variables and/or alter the input as needed.

This could look like the following examples:

def main_function():
    return main_helper(....)

def main_helper(...):
    <SOME_CODE>
    return main_helper(...)

def main_function():

    def main_helper(...):
        <SOME_CODE>
        return main_helper(...)

    return main_helper(....)

Consider the following questions

What can we use to tell if a number is factor of another number
What is true when a number is prime?
What is true when a number is not prime?

def is_prime(n):
    """Returns True if n is a prime number and False otherwise.

    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    "*** YOUR CODE HERE ***"

Q3: Find the Bug

Find and fix the bug 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
    384
    """
    if n == 2:
        return 2
    else:
        return n * skip_mul(n - 2)

Submit

If you attend the lab, you don't have to submit anything.

If you don't attend the lab, you will have to submit working code. Submit the lab13.py file on Canvas to Gradescope in the window on the assignment page.

Extra Practice

Q4: Hailstone

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

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

This sequence of values of n is often called a Hailstone sequence. Write 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:

Hint: When taking the recursive leap of faith, consider both the return value and side effect of this function.

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
    """