Skip to content

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

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