Study Guide: Recursion

Instructions

This is a study guide with links to past lectures, assignments, and handouts, as well as additional practice problems to assist you in learning the concepts.

Assignments

Important: For solutions to these assignments once they have been released, see the main website

Handouts

Lectures

Readings

Guides

Recursion

Recursion is a technique for solving a large computational problem by repeatedly applying the same procedure(s) to reduce it to successively smaller problems. A recursive procedure has two parts: one or more base cases and a recursive step.

Base cases are predetermined solutions for the simplest versions of the problem: if the given problem is a base case, no further computation is necessary to get the result.

The recursive step is a set of rules that eventually reduces all versions of the problem to one of the base cases when applied repeatedly.

Infinite recursion occurs if there is no base case or the recursive step does not make progress towards its base case(s).

def fn(input):
    if <base case>:
        return ...
    else:
        return <combine input and fn(input_reduced)>

An Analogy

Suppose you're waiting in line for a concert. You'd like to know where you are in line, but can't step out of line. What do you do? (Suppose you also have a friend with you.)

An iterative algorithm (a step-by-step procedure) might look like:

  1. Ask your friend to walk down to the front of the line.
  2. Then count one-by-one until they reach you.
  3. Once everyone's been counted, report your position to you.

This approach is like using a while loop with a counter to keep track of the current position and only at the end returning the final value.

A recursive algorithm, on the other hand, might look like:

  1. If we're at the front, we know we're first in line.
  2. Otherwise, we ask the person in front of us, "What number in line are you?"
  3. Once the person in front figures out their position and tells you, add 1 to their position to determine your position.

This only works if everyone in front of you follows the same algorithm. While it might not work in real life because others might not follow the same steps, in a computer, we can define a function that follows the same steps.

There are a couple points to notice about this analogy. There are two phases in evaluating a recursive function:

  • First, breaking down the problem by examining smaller and smaller problems. Each person asks the person in front of them, "What number in line are you?" We ask the person in front of us because they're closer to the front of the line. Each problem is broken down into smaller subproblems that approach the base case.
  • Second, building on the returned answer. Only the person at the front of the line knows their position by default, so when they turn around to report to the second person in line, the second person can't just take the answer the person in front reported: they also need to account for themselves by adding 1! In the same way, recursive programs need some way of adding on to the result of the recursive step.

Solving Recursive Problems

See the Studying Guide for more tips!

Recursive problems are solved similarly to the way we solve higher-order function problems.

  1. Understand the problem. Restate the problem in your own words, identify the domain (input), range (output), roughly define the behavior of the function.
  2. Study the examples and doctests. Develop smaller examples and identify the similarities and patterns between examples. Recursion relies on solving subproblems which implies that there is some relationship between the smaller problem and the larger problem.
  3. Identify similar problems. Is this question more easily solved with (linear) recursion or tree recursion?
  4. Adapt a solution. Identify the general idea of the similar problem and adapt it for this new context.
  5. Implement the solution in code and verify correctness by evaluating the function.

Functional Abstraction

Abstraction is a technique for managing complexity by hiding details that make programs complex and hard to understand.

Functional abstraction is a method for applying the idea of abstractions to functions, or pieces of code which accomplish specific tasks. Specifically, functional abstraction lets us reason about a program by answering three key questions.

  1. What is the domain, or possible set of inputs, we can pass to the function?
  2. What is the range, or possible set of outputs, that can be returned from the function?
  3. What is the behavior, or transformations that the function accomplishes along the way to compute the output? (So far, most of the functions we've written are pure functions, which mean they have no side-effects, so we can usually define the behavior with a mapping from the domain to the range.)

If we think about programs in terms of these three features, we can "black-box" programs and make larger leaps of logic.

Functional abstraction allows us to make claims about recursive programs and take the so-called recursive leap of faith. To believe that the recursive definition of factorial is correct without running the code to check requires us to believe that factorial is a function which maps inputs to outputs: factorial(4) just evaluates to 24, and that's a fact we can rely on when recursively defining factorial(5) in terms of factorial(4).

Enumeration

Functional abstraction, or the idea that pure functions are just a mapping from inputs to outputs, can be difficult to fully understand.

To help wrap our heads around this idea, let's revisit factorial from another angle. Suppose we knew nothing about recursion. Actually, let's up the stakes and suppose we didn't even know how to write a while or for loop. How could we define factorial?

One way is to enumerate all possibilities.

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1 * 1
    elif n == 2:
        return 2 * 1 * 1
    elif n == 3:
        return 3 * 2 * 1 * 1
    elif n == 4:
        return 4 * 3 * 2 * 1 * 1
    elif n == 5:
        # You can imagine how tedious this would get

This representation is useful for two reasons: it helps us visualize the arithmetic underlying computing the factorial of a number, and it also helps us see that factorial(n) just returns a particular number.

Suppose we wanted to define the case for n == 5 without having to rewrite all the preceding arithmetic. We could conveniently define a case for n == 5 in terms of n == 4, and we'd start to see the pattern: the factorial of 6, 7, 8 would just rely on the factorial of the previous value which we've proven is correctly defined.

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1 * 1
    elif n == 2:
        return 2 * 1 * 1
    elif n == 3:
        return 3 * 2 * 1 * 1
    elif n == 4:
        return 4 * 3 * 2 * 1 * 1
    elif n == 5:
        return 5 * factorial(4)
    elif n == 6:
        return 6 * factorial(5)
    else:
        return n * factorial(n - 1)

With a little more work, we can identify the redundancies in our 'arms-length' base cases and simplify the code.

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

Tree Recursion

A function is tree-recursive if the recursive step contains more than one call to the same function.

As a technique for solving problems, tree recursion allows us to explore multiple possibilities. Let's consider one such problem to help illustrate this example.

Solution Space

Suppose we want to count the number of combinations of dividing 6 pieces of chocolate amongst my friends, but we don't want to give any one friend more than 4 pieces.

How might we solve this problem?

One way is to simply count out all the possibilities. One possible combination involves giving out 1 piece to 6 friends.

6 = 1 + 1 + 1 + 1 + 1 + 1

Another combination might be to give 3 pieces to 2 friends. We can come up with some other combinations too.

6 = 3 + 3
6 = 2 + 4
6 = 1 + 3 + 2

But what about 6 = 4 + 2? Is that a valid combination if we've already counted 6 = 2 + 4? This is a good chance for us to revisit our problem statement and clarify our understanding of what the problem is asking.

Understand the problem: ask questions, study the examples, and come up with examples of your own. Each clarification we make now gives us insight into the structure of the problem which helps a lot because, in computer science, the structure of a problems is very often related to the shape of its solution.

These are combinations, so we're only interested in the different ways we can divide the problem without differentiating for who exactly receives which pieces. In other words, 6 = 4 + 2 is the same as 6 = 2 + 4 because we don't care who receives which pieces.

What about 6 = 1 + 3 + 2? Since we know that we're not differentiating between 6 = 3 + 2 + 1, 6 = 2 + 1 + 3, and 6 = 2 + 3 + 1, for example, how do we go about approaching this problem?

This brings us to one of the big challenges of solving tree-recursive problems.

How do we explore the solution space of all valid combinations? We'd like to write some code which can somehow model this complex process, but we don't quite know how to go about it? Where do we start with this problem? How do we capture its complexity now that we have to 'uncount' the duplicates?

Let's solve this problem by finding generality between examples. We'd ultimately like to come up with a general algorithm (step-by-step procedure) we can follow to search through all possible solutions. We should reorder our solution in a way that a computer can work with by reorganizing our solution space.

Suppose instead of listing out all combinations randomly, we take a structured approach to solving the problem. Let's list out all combinations, but always using the most possible pieces of chocolate first.

6 = 4 + 2
6 = 4 + 1 + 1
6 = 3 + 3
6 = 3 + 2 + 1
...

In reorganizing our solution space, we identified a strategy that we can always follow for generating each combination: we can always use the most possible pieces first before moving onto smaller pieces as necessary. We give out 4 pieces of chocolate to 1 friend which leaves us with 2 pieces to give out to everyone else. We can then solve that smaller problem by asking the question, "Count the number of combinations of dividing the remaining 2 pieces..." where the most pieces I can give out to any one friend is still something we need to determine through further experimentation.

Order of Recursive Calls

In lecture, we defined a function cascade that printed a mesmerizing cascade of numbers.

def cascade(n):
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n // 10)
        print(n)

Calling cascade(123) yields the following output.

123
12
1
12
123

Why is that the case? The best way to figure out is to try things out for yourself in Python Tutor.

Let's look at a tree-recursive variant of cascade called treecade.

def treecade(n):
    if n < 10:
        print(n)
    else:
        treecade(n // 10)
        print(n)
        treecade(n // 10)

Fully describe the behavior of this function. Then, try it out for yourself in the interactive interpreter or Python Tutor. Finally, answer the questions below to verify your understanding.

  1. Between treecade and cascade, which lines differ?
  2. How does Python keep track of all the separate values of n which are printed out?
  3. What happens after a call to treecade hits the base case? Where does Python go next?

Practice Problems

Easy

Q1: In sum...

Write a function sum that takes a single argument n and computes the sum of all integers between 0 and n inclusive. Assume n is non-negative.

def sum(n):
    """Computes the sum of all integers between 1 and n, inclusive.
    Assume n is positive.

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """

    "*** YOUR CODE HERE ***"

    if n == 1:
        return 1
    return n + sum(n - 1)

Q2: 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 sin(x) = 3sin(x/3) - 4sin³(x/3)

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

def sine(x):

    "*** YOUR CODE HERE ***"

    if abs(x) < 0.0001:
        return x
    return 3 * sine(x / 3) - 4 * pow(sine(x / 3), 3)

Q3: Countdown-Up

Write a function Countdown_up that takes a single argument n and simultaneously prints out the countdown from n to 0 and the countup from n to 2n, inclusive. Hint: We probably need to introduce another parameter, so maybe use a helper function!

def countdown_up(n):
    """Starts at n and simultaneously prints out the countdown from n to 0
    and the countup from n to 2*n, inclusive.

    >>> countdown_up(0)
    0

    >>> countdown_up(5)
    5
    4
    6
    3
    7
    2
    8
    1
    9
    0
    10
    """

    "*** YOUR CODE HERE ***"

    def helper(i):
        if i == 0:
            print(n)
        elif i > n:
            return
        else:
            print(n-i)
            print(n+i)
        helper(i + 1)

    helper(0)

Medium

Q4: Super Mario

Mario needs to jump over a sequence of Piranha plants, represented as a string of spaces (no plant) and P's (plant!). He only moves forward, and he can either step (move forward one space) or jump (move forward two spaces) from each position. How many different ways can Mario traverse a level without stepping or jumping into a Piranha plant? Assume that every level begins with a space (where Mario starts) and ends with a space (where Mario must end up):

Hint: You can get the ith character in a string s by using s[i]. For example,

>>> s = 'abcdefg'
>>> s[0]
'a'
>>> s[2]
'c'

You can find the total number of characters in a string with the built-in len function:

>>> s = 'abcdefg'
>>> len(s)
7
>>> len('')
0
def mario_number(level):
    """Return the number of ways that Mario can perform a sequence of steps
    or jumps to reach the end of the level without ever landing in a Piranha
    plant. Assume that every level begins and ends with a space.

    >>> mario_number(' P P ')   # jump, jump
    1
    >>> mario_number(' P P  ')   # jump, jump, step
    1
    >>> mario_number('  P P ')  # step, jump, jump
    1
    >>> mario_number('   P P ') # step, step, jump, jump or jump, jump, jump
    2
    >>> mario_number(' P PP ')  # Mario cannot jump two plants
    0
    >>> mario_number('    ')    # step, jump ; jump, step ; step, step, step
    3
    >>> mario_number('    P    ')
    9
    >>> mario_number('   P    P P   P  P P    P     P ')
    180
    """

    "*** YOUR CODE HERE ***"

    def ways(n):
        if n == len(level)-1:
            return 1
        if n >= len(level) or level[n] == 'P':
            return 0
        return ways(n+1) + ways(n+2)
    return ways(0)

Difficult

Q5: Knapsack

You're are a thief, and your job is to pick among n items that are of different weights and values. You have a knapsack that supports c pounds, and you want to pick some subset of the items so that you maximize the value you've stolen.

Define knapsack, which takes a list weights, list values and a capacity c, and returns that max value. You may assume that item 0 weighs weights[0] pounds, and is worth values[0]; item 1 weighs weights[1] pounds, and is worth values[1]; etc.

def knapsack(weights, values, c):
    """
    >>> w = [2, 6, 3, 3]
    >>> v = [1, 5, 3, 3]
    >>> knapsack(w, v, 6)
    6
    """

    "*** YOUR CODE HERE ***"

    if weights == []:
        return 0
    else:
        first_weight, rest_weights = weights[0], weights[1:]
        first_value, rest_values = values[0], values[1:]
        with_first = first_value + knapsack(rest_weights, rest_values, c-first_weight)
        without_first = knapsack(rest_weights, rest_values, c)
        if first_weight <= c:
            return max(with_first, without_first)
        return without_first

Q6: Y combinator

The recursive factorial function can be written as a single expression by using a conditional expression.

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120

However, this implementation relies on the fact (no pun intended) that fact has a name, to which we refer in the body of fact. To write a recursive function, we have always given it a name using a def or assignment statement so that we can refer to the function within its own body. In this question, your job is to define fact recursively without giving it a name!

There's actually a general way to do this that uses a function Y defined

def Y(f):
    return f(lambda: Y(f))

Using this function, you can define fact with an assignment statement like this:

 fact = Y(?)

where ? is an expression containing only lambda expressions, conditional expressions, function calls, and the functions mul and sub. That is, ? contains no statements (no assignments or def statements in particular), and no mention of fact or any other identifier defined outside ? other than mul or sub from the operator module. You are also allowed to use the equality (==) operator. Find such an expression to use in place of ?.

from operator import sub, mul

def Y(f):
    """The Y ("paradoxical") combinator."""
    return f(lambda: Y(f))

def Y_tester():
    """
    >>> tmp = Y_tester()
    >>> tmp(1)
    1
    >>> tmp(5)
    120
    >>> tmp(2)
    2
    """

    "*** YOUR CODE HERE ***"
    return Y(________)  # Replace 

    return Y(lambda f: lambda n: 1 if n==0 else n * f()(n-1))