Lab 03: Recursion

By the end of this lab, you should have submitted the `lab03` assignment using the command `submit lab03`.

This lab is due by 11:59pm on 07/03/2014.

Here is a lab03.py starter file for this lab.

Recursion

Warm Up: Recursion Basics

A recursive function is a function that calls itself in its body, either directly or indirectly. Recursive functions have two important components:

1. Base case(s), where the function directly computes an answer without calling itself. Usually the base case deals with the simplest possible form of the problem you're trying to solve.
2. Recursive case(s), where the function calls itself with a simpler argument as part of the computation.

Let's look at the canonical example, `factorial`:

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

We know by its definition that `0!` is `1`. So we choose `n = 0` as our base case. The recursive step also follows from the definition of factorial, i.e. `n! = n * (n-1)!`.

The next few questions in lab will have you writing recursive functions. Here are some general tips:

• Consider how you can solve the current problem using the solution to a simpler version of the problem. Remember to trust the recursion: assume that your solution to the simpler problem works correctly without worrying about how.
• Think about what the answer would be in the simplest possible case(s). These will be your base cases - the stopping points for your recursive calls. Make sure to consider the possibility that you're missing base cases (this is a common way recurisve solutions fail).

Question 1: Misconceptions

The following examples of recursive functions show some examples of common recursion mistakes. Fix them so that they work as intended.

``````def sum_every_number(n):
"""Return the sum of every natural number up to n, inclusive.

>>> sum_every_number(5)
15
"""
if n == 1:
return 0
else:
return n + sum_every_number(n - 1)``````

The base case is incorrect. If we call `sum_every_number(1)`, the answer should be 1, not 0.

``````def sum_every_number(n):
if n == 1:
return 1
else:
return n + sum_every_number(n - 1)``````

We could also change our base case to be when `n` is 0:

``````def sum_every_number(n):
if n == 0:
return 0
else:
return n + sum_every_number(n - 1)``````
``````def sum_every_other_number(n):
"""Return the sum of every other natural number
up to n, inclusive.

>>> sum_every_other_number(8)
20
>>> sum_every_other_number(9)
25
"""
if n == 0:
return 0
else:
return n + sum_every_other_number(n - 2)``````

Consider what happens when we choose an odd number for `n`. `sum_every_other_number(3)` will return `3 + sum_every_other_number(1)`. `sum_every_other_number(1)` will return `1 + sum_every_other_number(-1)`. You may see the problem now. Since we are decreasing `n` by two at a time, we've completed missed our base case of `n == 0`, and we will end up recursing indefinitely. We need to add another base case to make sure this doesn't happen.

``````def sum_every_other_number(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return n + sum_every_other_number(n - 2)``````
``````def fibonacci(n):
"""Return the nth fibonacci number.

>>> fibonacci(11)
89
"""
if n == 0:
return 0
elif n == 1:
return 1
else:
fibonacci(n - 1) + fibonacci(n - 2)``````

The result of the recursive calls is not returned.

``````def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)``````
``````def print_up_to(n):
"""Print every natural number up to n, inclusive.

>>> print_up_to(5)
1
2
3
4
5
"""
i = 1
if i > n:
return
else:
print(i)
i += 1
print_up_to(n)``````

When we first call `print_up_to`, we set a counter variable `i` to `1`. After we increment the counter, when we recurse and call `print_up_to` again, in the frame of the recursive call we actually create a new counter variable set to `1`. We are therefore not actually reducing toward the base case `i == n`. In order to keep track of information between recursive calls we need to pass the information as arguments to functions. Therefore, to solve this problem, we will use a helper function that we define so that we can choose which arguments to use.

``````def print_up_to(n):
def helper(i):
print(i)
if i < n:
helper(i + 1)
helper(1)``````

Note that in our helper function, we don't have a condition laid out as the base case as we normally do. The base case is implicit because we have the condition `i < n` under which we execute the recursive call, and we will stop recursing once `i == n` and we violate this condition.

Question 2

Write `map`, which takes a one argument function and a list as arguments, and returns a list of the results produced by applying the procedure to each element in the list.

``````def map(f, lst):
"""Returns a list of the results produced by applying f to each
element in lst.

>>> print_linked_list(map(lambda x: x * x, my_list))
< 1 4 9 16 >
bulbasaur
charmander
squirtle
< None None None >
"""
``````def map(f, lst):
if lst == empty:
return empty
else:

Question 3

The greatest common divisor of two positive integers `a` and `b` is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of `a` and `b` is one of the following:

• the smaller value if it evenly divides the larger value, OR
• the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if `a` is greater than `b` and `a` is not divisible by `b`, then

``gcd(a, b) == gcd(b, a % b)``

Write the `gcd` function recursively using Euclid's algorithm.

``````def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.

>>> gcd(0, 4)
4
>>> gcd(8, 0)
8
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
``````def gcd(a, b):
a, b = max(a, b), min(a, b)
if a % b == 0:
return b
else:
return gcd(b, a % b)``````

If you are curious, here is the iterative solution:

``````def gcd_iter(a, b):
if a < b:
return gcd_iter(b, a)
while a > b and not a % b == 0:
a, b = b, a % b
return b``````

Question 4: Hailstone

For the `hailstone` function from homework 1, you 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.

``````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
"""
``````def hailstone(n):
print(n)
if n == 1:
return 1
elif n % 2 == 0:
return 1 + hailstone(n // 2)
else:
return 1 + hailstone(3 * n + 1)``````

Question 5: Insect Combinatorics

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

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

``````def paths(m, n):
"""Return the number of paths from one corner to the opposite
corner of an M by N grid.

>>> paths(2, 2)
2
>>> paths(5, 7)
210
>>> paths(117, 1)
1
>>> paths(1, 157)
1
"""
``````def paths(m, n):