11/27¶
Announcements¶
- Project 3
- Part A due Tuesday, 11/28
- Part B due Thursday, 11/30
- Part C due Tuesday, 12/05
- Remember: Helping each other is fine. Copying code is not.
- Chapter 12: Recursion
- Also due Tuesday, 11/28
Recursion… Let's Write a Count Function¶
def count(items, key):
first = items[0]
rest = items[1:]
rest_count = rest.count(key)
if first == key:
return rest_count + 1
else:
return rest_count
No need to use the built-in count
method… We'll just use the count function we are writing!
def count(items, key):
first = items[0]
rest = items[1:]
rest_count = count(rest, key)
if first == key:
return rest_count + 1
else:
return rest_count
Problems??? What if items
is an empty list? There will be no first
element. We can fix that…
def count(items, key):
if len(items) == 0:
return 0
first = items[0]
rest = items[1:]
rest_count = count(rest, key)
if first == key:
return rest_count + 1
else:
return rest_count
Writing Recursive Functions¶
- Requirements:
- A base case that correctly handles the smallest version of the problem.
- The recursive case:
- Call the function to get the answer for a smaller version of the problem.
- Use that answer to provide the answer for the full version of the problem.
- If those steps are handled correctly, the final answer will be correct.
- No need to get tied in knots trying to understand what happens inside those recursive calls. Have faith in the process.
Tracing Recursive Functions¶
- On Paper
- In Thonny
- Using this nice Recursion Tree Visualizer
- EXERCISE
- Take a look at Dr. Mayfield's notes for today.
- For each example, draw the recursion trace and determine the return value.
Writing Recursive Functions¶
- Complete the following functions so that they correspond to the docstrings. The solutions must be recursive.
def contains(items, key):
"""Return True if the key is contained in items."""
def has_three(num):
"""Return True if the provided integer contains a 3 as any digit."""