Study Guide: Recursion
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.
Important: For solutions to these assignments once they have been released, see the main website
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)>
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:
- Ask your friend to walk down to the front of the line.
- Then count one-by-one until they reach you.
- 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:
- If we're at the front, we know we're first in line.
- Otherwise, we ask the person in front of us, "What number in line are you?"
- 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.
- Understand the problem. Restate the problem in your own words, identify the domain (input), range (output), roughly define the behavior of the function.
- 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.
- Identify similar problems. Is this question more easily solved with (linear) recursion or tree recursion?
- Adapt a solution. Identify the general idea of the similar problem and adapt it for this new context.
- Implement the solution in code and verify correctness by evaluating the function.
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.
- What is the domain, or possible set of inputs, we can pass to the function?
- What is the range, or possible set of outputs, that can be returned from the function?
- 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
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
factorial(5) in terms of
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
for loop. How could
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
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
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
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)
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.
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
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.
6 = 1 + 3 + 2? Since we know that we're not differentiating
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
def cascade(n): if n < 10: print(n) else: print(n) cascade(n // 10) print(n)
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
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.
cascade, which lines differ?
- How does Python keep track of all the separate values of
nwhich are printed out?
- What happens after a call to
treecadehits the base case? Where does Python go next?
Q1: In sum...
Write a function
sum that takes a single argument
and computes the sum of all integers between 0 and
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)
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)
Write a function
Countdown_up that takes a single argument
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)
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[i]. For example,
>>> s = 'abcdefg' >>> s 'a' >>> s 'c'
You can find the total number of characters in a string with the built-in
>>> 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)
You're 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
knapsack, which takes a list
values and a capacity
c, and returns that max value. You may assume that item 0 weighs
weights pounds, and is worth
values; item 1 weighs
pounds, and is worth
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, weights[1:] first_value, rest_values = values, 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
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
def Y(f): return f(lambda: Y(f))
Using this function, you can define
fact with an assignment statement
fact = Y(?)
where ? is an expression containing only lambda expressions,
conditional expressions, function calls, and the functions
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
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(________) # Replacereturn Y(lambda f: lambda n: 1 if n==0 else n * f()(n-1))