# 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:

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

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

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

- Between
`treecade`

and`cascade`

, which lines differ? - How does Python keep track of all the separate values of
`n`

which are printed out? - 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 theith 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))
```