Week 3 Exercises: Recursion¶
Recursion is super fun!
There are two sections: recursive functions to compute things and recursive functions to draw things!
Computing¶
For each of these problems, define the base case and the recursive case! I’ve done the first one for you.
Find the Minimum of a List¶
Use a recursive function to find the mininum of a list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | def minimum_of_list(some_list):
# base case
if len(some_list) == 1:
# return that item!
return some_list[0]
#recursive case
else:
# get the length of the list
n = len(some_list)
# find the halfway point
halfway = n // 2
# use recursion to find the minimum of the left side
min_left = minimum_of_list(some_list[:halfway])
# use recursion to find the minimum of the right side
min_right = minimum_of_list(some_list[halfway:])
# return the smallest one
if min_left < min_right:
return min_left
else:
return min_right
def run():
assert 1 == minimum_of_list([1,2,3])
assert -10 == minimum_of_list([1,-10,3])
assert 4 == minimum_of_list([10,20,4])
|
Test for a Palindrome¶
A palindrome is the same forwards as it is backwards. There could be several ways to do this. One way:
- Check to see if the ends are the same
-
some_string[0] == some_string[-1]
- Call the function on the string without the ends
-
new_string = old_string[1:-1]
- The base case: + The string is empty or of length 1
- The recursive case
+ Check to see if the ends are equal
+ Check to see if the interior is a palindrome
+ return the
and
of the result
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def is_palindrome(some_string):
if len(some_string) <= 1:
return True
else:
### fill in code here
def run():
assert is_palindrome('bob') == True # do I need to have the == though?
assert is_palindrome('wow') # no!
assert not is_palindrome('potato')
assert is_palindrome('mirror image|egami rorrim')
|
Hailstone Sequence¶
A hailstone sequence is a sequence with the following operations:
For each number, if the number is even, the new number is that number divided by 2. If it is odd, the new number is that number times 3 plus 1. This is repeated until the new number is 1.
More precisely:
1 2 3 4 | if n%2 == 0:
n = n // 2
else:
n = n*3 + 1
|
Write a function which computes the length of the hailstone sequence
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def hailstone_length(n):
#base case:
if n == 1:
return 1
def run():
assert hailstone_length(1) == 1
assert hailstone_length(2) == 2
assert hailstone_length(3) == 8
assert hailstone_length(4) == 3
assert hailstone_length(5) == 6
assert hailstone_length(6) == 9
assert hailstone_length(7) == 17
assert hailstone_length(8) == 4
assert hailstone_length(9) == 20
|