# Discussion 3: Recursion, Tree Recursion

## Vitamin

The vitamin for Discussion 3 is worth 1 point and located here.

# Recursion

A *recursive* function is a function that is defined in terms of itself. Consider this recursive `factorial`

function:

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

Although we haven’t finished defining `factorial`

, we are still able to call it since the function body is not evaluated until
the function is called. When `n`

is 0 or 1, we just return 1. This is known as the *base case*, and it prevents the
function from infinitely recursing. Now we can compute `factorial(2)`

in terms of `factorial(1)`

, and `factorial(3)`

in terms of
`factorial(2)`

, and `factorial(4)`

– well, you get the idea.

There are **three** common steps in a recursive definition:

**Figure out your base case:**The base case is usually the simplest input possible to the function. For example,`factorial(0)`

is 1 by definition. You can also think of a base case as a stopping condition for the recursion. If you can’t figure this out right away, move on to the recursive case and try to figure out the point at which we can’t reduce the problem any further.**Make a recursive call with a simpler argument:**Simplify your problem, and assume that a recursive call for this new problem will simply work. This is called the “leap of faith”. For`factorial`

, we reduce the problem by calling`factorial(n - 1)`

.**Use your recursive call to solve the full problem:**Remember that we are assuming the recursive call works. With the result of the recursive call, how can you solve the original problem you were asked? For`factorial`

, we just multiply (n − 1)! by n.

Another way to understand recursion is by separating out two things: "internal correctness" and not running forever (known as "halting").

A recursive function is internally correct if it is always does the right thing assuming that every recursive call does the right thing.

Consider this alternative recursive `factorial`

:

```
def factorial(n): # WRONG!
if n == 2:
return n
return n * factorial(n-1)
```

It is internally correct, since 2! = 2 and n! = n ∗ (n − 1)! are both true statements.

However, that `factorial`

does not halt on all inputs, since `factorial(1)`

results in a call to `factorial(0)`

, and then to `factorial(-1)`

and so on.

A recursive function is correct if and only if it is both internally correct and halts for valid inputs; but you can check each property separately. The "recursive leap of faith" is temporarily placing yourself in a mindset where you only check internal correctness.

### Q1: Warm Up: Recursive Multiplication

These exercises are meant to help refresh your memory of topics covered in lecture and/or lab this week before tackling more challenging problems.Write a function that takes two numbers `m`

and `n`

and returns their product. Assume `m`

and `n`

are positive integers. Use **recursion**, not `mul`

or `*`

!

Hint:

`5 * 3 = 5 + (5 * 2) = 5 + 5 + (5 * 1)`

.

For the base case, what is the simplest possible input for multiply?

**Solution**: If one of the inputs is one, you simply return the other input.

For the recursive case, what does calling `multiply(m - 1, n)`

do? What does calling `multiply(m, n - 1)`

do? Do we prefer one over the other?

**Solution**: The first call will calculate a value that is

`n`

less than the total, while the second will calculate a value that is `m`

less.
Either recursive call will work, but only `multiply(m, n - 1)`

is used in this solution.
**Your Answer**Run in 61A Code

**Solution**

```
def multiply(m, n):
""" Takes two positive integers and returns their product using recursion.
>>> multiply(5, 3)
15
"""
if n == 1:
return m
else:
return m + multiply(m, n - 1)
# TAIL RECURSIVE SOLUTION
def multiply_helper(x, y, result):
if y == 0:
return result
else:
return multiply_helper(x, y - 1, result + x)
return multiply_helper(m, n, 0)
```

### Q2: Recursion Environment Diagram

Draw an environment diagram for the following code:

```
def rec(x, y):
if y > 0:
return x * rec(x, y - 1)
return 1
rec(3, 2)
```

**Your Answer**

Return value |

Return value |

Return value |

**Solution**

Imagine you were writing the documentation for this function. Come up with a line that describes what the function does:

**Solution:**This function returns the result of computing X to the power of Y.

You may also want to watch this video walkthrough.

Note: This problem is meant to help you understand what really goes on when we make the "recursive leap of faith". However, when approaching or debugging recursive functions, you should avoid visualizing them in this way for large or complicated inputs, since the large number of frames can bes quite unwieldy and confusing. Instead, think in terms of the three step process - base case, recursive call, solving the full problem.

### Q3: Merge Numbers

Write a procedure `merge(n1, n2)`

which takes numbers with digits in decreasing order
and returns a single number with all of the digits of the two, in decreasing order.
Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.

Hint: If you can figure out which number has the smallest digit out of both, then we know that the resulting number will have that smallest digit, followed by the merge of the two numbers with the smallest digit removed.

**Your Answer**Run in 61A Code

**Solution**

```
def merge(n1, n2):
""" Merges two numbers by digit in decreasing order
>>> merge(31, 42)
4321
>>> merge(21, 0)
21
>>> merge (21, 31)
3211
"""
if n1 == 0:
return n2
elif n2 == 0:
return n1
elif n1 % 10 < n2 % 10:
return merge(n1 // 10, n2) * 10 + n1 % 10
else:
return merge(n1, n2 // 10) * 10 + n2 % 10
```

### Q4: Recursive Hailstone

Recall the `hailstone`

function from Homework 1.
First, 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.

Hint: When taking the recursive leap of faith, consider both the return value and side effect of this function.

**Your Answer**Run in 61A Code

**Solution**

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

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

. We implemented
this in Discussion 1 iteratively, now time to do it recursively!

Hint: You will need a helper function! Remember helper functions are useful if you need to keep track of more variables than the given parameters, or if you need to change the value of the input.

**Your Answer**Run in 61A Code

**Solution**

```
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
"""
def helper(i):
if i > (n ** 0.5): # Could replace with i == n
return True
elif n % i == 0:
return False
return helper(i + 1)
return helper(2)
```

# Tree Recursion

Consider a function that requires more than one recursive call. A simple example is the recursive `fibonacci`

function:

```
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
```

This type of recursion is called `tree recursion`

, because it makes more than one recursive call in its recursive case. If we draw out the recursive calls, we see the recursive calls in the shape of an upside-down tree:

We could, in theory, use loops to write the same procedure. However, problems that are naturally solved using tree recursive procedures are generally difficult to write iteratively. It is sometimes the case that a tree recursive problem also involves iteration: for example, you might use a while loop to add together multiple recursive calls.

As a general rule of thumb, whenever you need to try multiple possibilities at the same time, you should consider using tree recursion.

### Q6: Count Stair Ways

Imagine that you want to go up a flight of stairs that has `n`

steps, where `n`

is a positive integer. You can either take 1 or 2 steps each time. In this question, you'll write a function `count_stair_ways`

that solves this problem. Before you code your approach, consider these questions.

How many different ways can you go up this flight of stairs?

**Solution**: When there is only one step, there is only one way to go up the stair. When there are two steps, we can go up in two ways: take a single 2-step, or take two 1-steps.

What’s the base case for this question? What is the simplest input?

**Solution**: Our first base case is when there is one step left. This is, by definition, the smallest input since it is the smallest positive integer. Our second base case is when we have two steps left. We need this base case for a similar reason that

`fibonacci`

needs 2 base cases -- to cover both recursive calls.
**ALTERNATE Solution**: Our first base case is where there are no steps left. This means that we took an action in the previous recursive step that led to our goal of reaching the top. Our second base case is where we have overstepped. This means that the action we took is not valid, as it caused us to step over our goal.

What do `count_stair_ways(n - 1)`

and `count_stair_ways(n - 2)`

represent?

**Solution**:

`count_stair_ways(n - 1)`

represents the number of different ways to go up the last `n−1`

stairs (this is the case where we take 1 step as our move). `count_stair_ways(n - 2)`

represents the number of different ways to go up the last `n−2`

stairs (this is the case where we take 2 steps as our move). Our base cases will take care of the situations where there are no steps left or we overstepped.
**Solution**: When there is only 1 step, there is only one way to go up the stair. When there are two steps, we can go up in two ways: take a single two-step, or take two one-steps.

Fill in the code for `count_stair_ways`

:

**Your Answer**Run in 61A Code

**Solution**

```
def count_stair_ways(n):
"""Returns the number of ways to climb up a flight of
n stairs, moving either 1 step or 2 steps at a time.
>>> count_stair_ways(4)
5
"""
if n == 1:
return 1
elif n == 2:
return 2
return count_stair_ways(n-1) + count_stair_ways(n-2)
```

`count_stair_ways(4)`

:
Check out these video walkthroughs explaining the approach:

### Q7: Count K

Consider a special version of the `count_stair_ways`

problem, where instead of taking 1 or 2 steps, we are able to take up to and including `k`

steps at a time. Write a function `count_k`

that figures out the number of paths for this scenario. Assume `n`

and `k`

are positive.

**Your Answer**Run in 61A Code

**Solution**

```
def count_k(n, k):
""" Counts the number of paths up a flight of n stairs
when taking up to and including k steps at a time.
>>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 1
4
>>> count_k(4, 4)
8
>>> count_k(10, 3)
274
>>> count_k(300, 1) # Only one step at a time
1
"""
if n == 0:
return 1
elif n < 0:
return 0
else:
total = 0
i = 1
while i <= k:
total += count_k(n - i, k)
i += 1
return total
```

Here's a tree of the calls made to `count_k(3, 3)`

:

# Exam prep

We recommending reading sections 1.7 from the textbook for these problems. We also recommend watching the June 29 and June 30 lectures on recursion and tree recursion, respectively.

Test your work! For example, for `is_palindrome`

, you can type `test(is_palindrome)`

in the python interpreter you get once you click Run in 61A Code to verify if you pass the doctests or not.

**IMPORTANT: you may not use any string operations other than indexing, len and slicing. Specifically, you may not call reversed or index with a negative step size.**

Here is a brief survey of string operations useful to this worksheet. Given a string `s = 'abcdefg'`

,

`len(s)`

evaluates to the length of`s`

, in this case`6`

`s[0]`

evaluates to the leftmost character of`s`

, in this case`'a'`

`s[-1]`

, or alternatively`s[len(s) - 1]`

, evaluates to the rightmost character of`s`

, in this case`g`

`s[a:b]`

evaluates to a slice of`s`

from position`a`

to just before position`b`

, zero-indexed for both. So`s[2:5]`

would give`cde`

`s[1:]`

evaluates to a slice of`s`

from position`1`

until the end, in this case`bcdefg`

`s[:-1]`

, or alternatively`s[:len(s)-1]`

, evaluates to a slice of`s`

from the beginning until one position before the end, in this case`abcdef`

- Equality can be used as normal. For example,
`s == 'abcdefg'`

evaluates to`True`

, and`s == 'egg'`

evaluates to`False`

.

### Q8: 'Tis it?

**Difficulty: ⭐**

A palindrome is a string that remains identical when reversed. Given a string `s`

, `is_palindrome`

should return whether or not `s`

is a palindrome.

**IMPORTANT:** Please use the template for this problem; if you have spare time, try to solve the problem using iteration without the template.

**Your Answer**Run in 61A Code

**Solution**

```
def is_palindrome(s):
"""
>>> is_palindrome("tenet")
True
>>> is_palindrome("tenets")
False
>>> is_palindrome("raincar")
False
>>> is_palindrome("")
True
>>> is_palindrome("a")
True
>>> is_palindrome("ab")
False
"""
if len(s) <= 1: return True
return s[0] == s[-1] and is_palindrome(s[1:-1])
```

### Q9: Greatest Pals

**Difficulty: ⭐⭐**

A *substring* of `s`

is a sequence of consecutive letters within `s`

. Given a string `s`

, `greatest_pal`

should return the longest palindromic substring of `s`

. If there are multiple palindromic substrings of greatest length, then return the leftmost one. **You may use is_palindrome.**

**IMPORTANT:** For this problem, each starter code template is just a suggestion. We recommend that you use the first, but feel free to modify it, try one of the other two or write your own if you'd like to. Comment out the other versions of the function to run doctests.

**Your Answer**Run in 61A Code

**Solution**

```
def greatest_pal(s):
"""
>>> greatest_pal("tenet")
'tenet'
>>> greatest_pal("tenets")
'tenet'
>>> greatest_pal("stennet")
'tennet'
>>> greatest_pal("25 racecars")
'racecar'
>>> greatest_pal("abc")
'a'
>>> greatest_pal("")
''
"""
if is_palindrome(s): return s
left, right = greatest_pal(s[:-1]), greatest_pal(s[1:]) if len(left) >= len(right): return left return right
def greatest_pal(s):
"""
>>> greatest_pal("tenet")
'tenet'
>>> greatest_pal("tenets")
'tenet'
>>> greatest_pal("stennet")
'tennet'
>>> greatest_pal("25 racecars")
'racecar'
>>> greatest_pal("abc")
'a'
>>> greatest_pal("")
''
"""
def helper(a, b, c):
if a > len(s): return c elif b > len(s) - a: return helper(a+1, 0, c) elif is_palindrome(s[b:b+a]) and a > len(c): c = s[b:b+a] return helper(a, b+1, c) return helper(1, 0, "")
def greatest_pal(s):
"""
>>> greatest_pal("tenet")
'tenet'
>>> greatest_pal("tenets")
'tenet'
>>> greatest_pal("stennet")
'tennet'
>>> greatest_pal("25 racecars")
'racecar'
>>> greatest_pal("abc")
'a'
>>> greatest_pal("")
''
"""
def helper(a, b):
if b > len(s) - a: return helper(a-1, 0) elif is_palindrome(s[b:b+a]): return s[b:b+a] return helper(a, b+1) return helper(len(s), 0)
```

### Q10: Wait, It's All Palindromes?

**Difficulty: ⭐⭐⭐**

Given a string `s`

, return the longest palindromic substring of `s`

. If there are multiple palindromes of greatest length, then return the leftmost one. **You may not use is_palindrome.**

**Hint:** Given equivalent values `a`

and `b`

, `max(a, b)`

will evaluate to `a`

. You may also find the `key`

argument to `max`

helpful.

**Your Answer**Run in 61A Code

**Solution**

```
def greatest_pal_two(s):
"""
>>> greatest_pal_two("tenet")
'tenet'
>>> greatest_pal_two("tenets")
'tenet'
>>> greatest_pal_two("stennet")
'tennet'
>>> greatest_pal_two("abc")
'a'
>>> greatest_pal_two("")
''
"""
for i in range(len(s) // 2): if s[i] != s[-(i+1)]: return max(greatest_pal_two(s[:-1]), greatest_pal_two(s[1:]), key=len) return s
```

## Just for Fun

**This is a challenge problem and not reflective of exam difficulty.**We will not be going over this problem in examprep section, but we will be releasing solutions.

### Q11: All-Ys Has Been

**Difficulty: 😨**

Given mystery function `Y`

, complete `fib`

and `is_pal`

so that the given doctests work correctly. When `Y`

is called on `fib`

, it should return a function which takes a positive integer `n`

and returns the `n`

th Fibonacci number.

Similarly, when `Y`

is called on `is_pal_maker`

it should return a function `is_pal`

that takes a string `s`

and returns whether `s`

is a palindrome.

**Hint:** You may use the ternary operator `<a> if <bool-exp> else <b>`

, which evaluates to `<a>`

if `<bool-exp>`

is truthy and evaluates to `<b>`

if `<bool-exp>`

is false-y.

**Your Answer**Run in 61A Code

**Solution**

```
Y = lambda f: (lambda x: x(x))(lambda x: f(lambda z: x(x)(z)))
fib_maker = lambda f: lambda r: r if r <= 1 else f(r-1) + f(r-2)is_pal_maker = lambda f: lambda r: True if len(r) <= 1 else r[0] == r[-1] and f(r[1:-1])
fib = Y(fib_maker)
is_pal = Y(is_pal_maker)
# This code sets up doctests for fib and is_pal. Run test(fib) and test(is_pal) to check your implementation
fib.__name__ = 'fib'
fib.__doc__="""Given n, returns the nth Fibonacci nuimber.
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
"""
is_pal.__name__ = 'is_pal'
is_pal.__doc__="""Returns whether or not an input string s is a palindrome.
>>> is_pal('tenet')
True
>>> is_pal('tenets')
False
>>> is_pal('ab')
False
>>> is_pal('')
True
>>> is_pal('a')
True
"""
```