Nov 28: Tracing Recursion

Learning Objectives

After today's class, you should be able to:

  • Describe the process of tracing a recursive function on paper
  • Explain the steps for writing a recursive function in Python
  • Access data from JSON files

Announcement

  • Programming Assignment 3 PA 3
    • Part A due TODAY Nov 28th
    • Part B due Thursday Nov 30th
    • Part C due Wednesday Dec 6th

Today's class

From last week: JSON Datasets 15 minutes

  • CORGIS
    • Collection of Really Great, Interesting, Situated Datasets
  • Example: County Demographics

JSON Example 

import json
from pprint import pprint

with open("county_demographics.json") as file:
    data = json.load(file)  # dictionary

for item in data:
    if item["County"] == "Harrisonburg city":
        pprint(item)

  • Add code to print counties whose percent 65 and older is greater than 30%
for item in data:
    if item["Age"]["Percent 65 and Older"] > 30.0:
        print(item["County"])

Inclass Activity: 25 minutes

Recursion: 30 minutes

  • Start Thonny and use the debugger

  • python tutor

  • Factorial

    • 0! = 1
    • n! = n * (n-1)!

def fn(n):
    if (n == 0):
        return 1
    return n * fn(n - 1)
How to Write a recursive function

  1. Base case: how will the recursion stop?
  2. Current case: what needs to be computed?
  3. Recursion: how will the arguments change?

Examples

  • sum digits 
    # Add the digits of a positive integer.


def sum_digits(n):
    if n == 0:
        return 0
    last = n % 10
    rest = n // 10
    return last + sum_digits(rest)


if __name__ == "__main__":
    print(f"{sum_digits(149) = }")
  • n choose k 
    # Compute "n choose k" which is known as the binomial coefficient.
# https://en.wikipedia.org/wiki/Binomial_coefficient#Recursive_formula


def choose(n, k):
    if k == 0 or k == n:
        return 1
    return choose(n-1, k-1) + choose(n-1, k)


if __name__ == "__main__":
    print(f"{choose(4, 2) = }")
  • count string 
    # Count how many times "hi" is in a string.


def count_hi(string):
    if len(string) < 2:
        return 0
    add = 0
    if string[0] == 'h' and string[1] == 'i':
        add = 1
    return add + count_hi(string[1:])


if __name__ == "__main__":
    print(f'{count_hi("This hint") = }')

Your To-Do List

PA 3

Prepare for Quiz 6A on Thursday

  • Nest data
  • List comprehension
  • Recursion
  • Python program using JSON data