Discussion 3: Recursion

Files: disc03.pdf

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything.

They say in order to understand recursion, you need to understand recursion, which you can read about here.

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.

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

Practice

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: Recursion Environment Diagram

Draw an environment diagram for the following code:

def recurse(x, y):
    if y > 0:
        return x * recurse(x, y - 1)
    return 1
recurse(3, 2)

Imagine you were writing the documentation for this function. Come up with a line that describes what the function does.

Note: This exercise is meant to help you understand what really goes on when we make the "recursive leap of faith". However, when approaching or debugging recursive functions, avoid visualizing them in this way for large or complicated inputs, since the large number of frames can be quite unwieldy and confusing. Instead, think in terms of the three steps: base case, recursive call, and solving the full problem.

Q3: 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 ***"

More Practice :)

Q4: Find the Bug

Find 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)

Q5: Fibonacci Sequence

The Fibonacci Sequence is one of the most famous sequences of numbers. The first and second terms are pre-defined as 0 and 1. Each term after is the sum of the previous two terms: 0 1 1 2 3 5 8 13 21 34 ...

Write a function that returns in the n_th term in the fibonacci sequence.

def fib(n):
    """Return the n_th term in the fibonacci sequence
    >>> fib(0)
    0
    >>> fib(1)
    1
    >>> fib(7)
    13
    >>> fib(23)
    28657
    """
    "*** YOUR CODE HERE ***"

Q6: Recursive Hailstone

Recall the hailstone function from Homework 1. First, 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.

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
    """
    "*** YOUR CODE HERE ***"

Q7: Merge Numbers

Write a procedure merge(n1, n2) which takes numbers with digits in decreasing order and returns a single number with all of the digits of the two, in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.

Hint: If you can figure out which number has the smallest digit out of both, then we know that the resulting number will have that smallest digit, followed by the merge of the two numbers with the smallest digit removed.

def merge(n1, n2):
    """ Merges two numbers by digit in decreasing order
    >>> merge(31, 42)
    4321
    >>> merge(21, 0)
    21
    >>> merge (21, 31)
    3211
    """
    "*** YOUR CODE HERE ***"