Nov 18: Tracing Recursion by Hand

Learning Objectives

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

• Explain how a return statement works in a recursive function.
• Describe the process of tracing a recursive function on paper.
• Step through a recursive function using Thonny's debugger.

Announcements

• Project 3: Music Data
  • Part A Unit Testing: Due Wednesday 11/19 15 points
  • Part B Nested: Due Friday 11/21 50 points
  • Part C Recursion: Due Wednesday 12/03 15 points
  • Part D API Usage: Due Wednesday 12/03 20 points

Math Examples

• Quick review of Thursday's activity
• Demo: Recursion Tree Visualizer

Factorial Function

• In Math:

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

• In Python:

  def fn(n):
      if (n == 0):
          return 1
      return n * fn(n - 1)
  

Binomial Coefficient

See explanation on Wikipedia

• In Math:
  • \({n \choose 0} = {n \choose n} = 1\)
  • \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\)
• In Python:

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

How to Trace

How to read a recursive function:

• On paper: drawing a diagram
• On computer: Thonny debugger

Example 1: 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) = }")

Example 2: n choose k

# Compute "n choose k" which is known as the binomial coefficient.


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) = }")

Example 3: 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") = }')

Example 4: search array

# Determine whether a list contains the number 6.


def has_six(nums, index):
    if index >= len(nums):
        return False
    return nums[index] == 6 or has_six(nums, index+1)


if __name__ == "__main__":
    print(f'{has_six([2, 5, 6], 0) = }')

Recursive Art

Example 5: Sierpiński Triangle

import turtle


def sierpinski_triangle(order, size):

    if order == 0:
        for _ in range(3):
            turtle.forward(size)
            turtle.left(120)
        return

    size /= 2

    sierpinski_triangle(order - 1, size)
    turtle.forward(size)

    sierpinski_triangle(order - 1, size)
    turtle.backward(size)
    turtle.left(60)
    turtle.forward(size)
    turtle.right(60)

    sierpinski_triangle(order - 1, size)
    turtle.left(60)
    turtle.backward(size)
    turtle.right(60)


def main():

    screen = turtle.Screen()
    w = screen.window_width()
    h = screen.window_height()
    size = 0.9 * min(w, h)

    screen.bgcolor("white")
    screen.title("Sierpinski Triangle")

    turtle.speed(10)
    turtle.penup()
    turtle.goto(-size/2, -size/2)
    turtle.pendown()

    order = int(input("Enter the order of the Sierpinski triangle: "))

    sierpinski_triangle(order, size)
    screen.exitonclick()


if __name__ == "__main__":
    main()

Going Further

Just for fun, check out this Introduction to Turtle and Graphical Recursion from Williams College (Fall 2022).

File Systems

• Folders contain files and other folders, which contain files and other folders
  • An everyday example of recursion!
• Two kinds of paths
  • An "absolute" path (from root of the file system) begins with a slash
  • A "relative" path (from the current folder) does not begin with a slash

Example

• Absolute path to cs149-simmonsj folder: /Users/simmonsj/Documents/git-repos/cs149-simmonsj (begins with a slash)
• Relative path to selected file: cs149-simmonsj/Website (does not begin with a slash)
• Absolute path to selected file: /Users/simmonsj/Documents/git-repos/cs149-simmonsj/Website

Using os and os.path

os – Miscellaneous operating system interfaces

• os.getcwd() – get current working directory
• os.listdir() – get list of directory entries

os.path – Common pathname manipulations

• os.path.isfile(path) – True if regular file
• os.path.basename(path) – get name of the file
• os.path.join(path, path2) – combine two paths

Example: print_files

A recursive function that "walks" the file system:

"""Example function for walking a file system.
"""

import os
import sys


def print_files(path, indent=0):
    """Print all files reachable from the given path.

    Each level of the file system should be indented by four spaces.
    Print a colon after paths that represent a folder (directory).

    Args:
        path (str): The starting (current) location.
        indent (int): How many leading spaces to print.
    """
    print(" " * indent, end="")
    basename = os.path.basename(path)

    # Base case: regular file
    if os.path.isfile(path):
        print(basename)
        return

    # Recursive case: folder
    print(basename + ":")
    for entry in sorted(os.listdir(path)):
        entry_path = os.path.join(path, entry)
        print_files(entry_path, indent + 4)


if __name__ == "__main__":
    if len(sys.argv) == 1:
        # no arguments; use current directory
        print_files(os.getcwd())
    else:
        # use the first command-line argument
        print_files(sys.argv[1])