Lab 13 - Recursion

Due by 11:59pm on 2024-02-29.

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 in Recursion

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

Try doing Q1: Find the Bug and Q2: Recursive Multiplication.

Translating Iteration to Recursion

Consider the Virahanka-Fibonacci sequence. You may have seen before that you can implement this sequence recursively like below, but it is very inefficient because it may compute a certain vir_fib(n)'s several times.

def vir_fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return vir_fib(n-1) + vir_fib(n-2)

f6-vir-fib

Consider the iterative implementation for the Virahanka-Fibonacci sequence that only computes vir_fib(n) once.

It will be helpful working through this algorithm.

def vir_fib(n):
    i = 0
    curr_num = 0
    next_num = 1
    while i < n:
        tmp = next_num
        next_num = curr_num + next_num
        curr_num = tmp
        i += 1

    return curr_num

It would be nice if we could have a recursive function that only computes any vir_fib(n) once.

Most, if not all, iterative solutions can be done recursively; however, when trying to do so, it can be difficult to figure out how to maintain similar efficiency within a recursive definition.

Consider: Is there a recursive function call on vir_fib() that can prevent us from computing certain vir_fib(n)'s multiple times and maintain similar efficiency as the iterative implementation?

No (however, you can get close by using memoization). In order to have the same efficiency as the iterative implementation, we have to keep track of multiple variables. To do this within a recursive function, we need to create an additional function that helps us do it - a helper function! This helper function will contain additional parameters that will be used as the additional variables in the iterative implementation not found in the recursive implementation. This helper function will do all the recursing to find the solution, and our original function will simply call this helper function with the correct starting values.

def vir_fib(n):

    def vir_fib_helper(i, curr_num, next_num):
        if i >= n:
            return curr_num
        else:
            return vir_fib_helper(i+1, next_num, curr_num+next_num)

    return vir_fib_helper(0,0,1)

Note: The vir_fib() function is often referred to as a wrapper function as it wraps around vir_fib_helper() and hides its usage.

The additional parameters that our recursive helper function need are i, curr_num, next_num. (tmp can is just a version of next_num, so it does not need to be a parameter. Ultimately, it is not needed at all.) We call this helper function with the arguments 0, 0, 1 (the same bindings used in the iterative implementation). The condition in the while loop will be flipped logically and used as the base case. The while loop's body will likely be used in the recursive case and call.

Compare and Contrast the iterative and recursive solution to the vir_fib(n) function. What is the same? What is different?

Iterative Recursive

Iterative	Recursive
`def vir_fib(n): i = 0 curr_num = 0 next_num = 1 while i < n: tmp = next_num next_num = curr_num + next_num curr_num = tmp i += 1 return curr_num`	`def vir_fib(n): def vir_fib_helper(i, curr_num, next_num): if i >= n: return curr_num else: return vir_fib_helper(i+1, next_num, curr_num+next_num) return vir_fib_helper(0,0,1)`

def vir_fib(n):
    i = 0
    curr_num = 0
    next_num = 1
    while i < n:
        tmp = next_num
        next_num = curr_num + next_num
        curr_num = tmp
        i += 1

    return curr_num

def vir_fib(n):

    def vir_fib_helper(i, curr_num, next_num):
        if i >= n:
            return curr_num
        else:
            return vir_fib_helper(i+1, next_num, curr_num+next_num)

    return vir_fib_helper(0,0,1)

The helper function can be defined within another function or outside of it. What is the difference? Why does vir_fib_helper() not need a n parameter? Additionally, why not let vir_fib_helper() become the new vir_fib()? What would you have to do to call this modified vir_fib()? What if we use default parameters? What are some potential drawbacks and benefits or using default parameters?

Try doing Q3: Is Prime

Required Questions

Q1: 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)

Test your code:

python3 -m pytest test_lab13.py::test_skip_mul

Q2: 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 including zero. 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 (including zero) and returns their product using recursion.
    >>> multiply(5, 3)
    15
    """
    "*** YOUR CODE HERE ***"

Test your code:

python3 -m pytest test_lab13.py::test_multiply

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.

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

Test your code:

python3 -m pytest test_lab13.py::test_is_prime

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

Q5: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (1, 1), and wants to end up at the top right corner, (M, N). 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.)

insect-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 different paths (only 3 are shown above).

Hint: What happens if we hit the top or rightmost edge?

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

This is a tree recursion problem. You will need two recursive function calls to paths() when appropriate.

Additional Info

Memoization

We can keep track of all of the different inputs in a dictionary that will allow us to recall the numbers that we have already computed. The function will keep previous calls in a dictionary to reduce redundant recursion.

memo={0:0, 1:1}
def vir_fib_memo(n):
    if n in memo:
        return memo[n]
    else:
        answer_at_n = vir_fib_memo(n-1) + vir_fib_memo(n-2)
        memo[n] = answer_at_n
        return memo[n]

This is not as efficient as the implementation with the helper function as it has to store and read the results the from dictionary.