Day 20 - Recursive functions by examples

Discovering Recursive Definitions by Example

1. Introduction (10 minutes)

• Context & Motivation:
  • Recap that students now know about structured and conditional data, and that lists (built with [list: ...]) are a kind of structured data with two parts: a first element and the rest (which is itself a list).
  • Explain that although we’ve computed with lists using for loops, another powerful approach is to process lists recursively.
• Learning Goals:
  • Understand that every non-empty list has a “first” and a “rest.”
  • Use examples to see a pattern for computing over lists recursively.
• Do Now:
  • Ask: “Consider the list [list: 4, 7, 9]. What is its first element? What is its rest?”
  • Have students share: First is 4, rest is [list: 7, 9]; then note that the rest’s first is 7 and its rest is [list: 9], and so on.

---

2. Using Examples to “Discover” Recursive Functions (25 minutes)

• Example 1: Computing the Length of a List (my-len)
  • Step-by-Step Examples:
    • Case 1: my-len(empty) is 0.
    • Case 2: my-len([list: 5]) is 1.
    • Case 3: my-len([list: 4, 7, 9]) is 3.
      • Notice: The first element is 4, and the rest is [list: 7, 9], which has length 2.
      • So we can say: my-len([list: 4, 7, 9]) is 1 + my-len([list: 7, 9]).
  • Discussion:
    • Ask: “How do these examples reveal a pattern?”
      Answer: An empty list has length 0, and a non-empty list’s length is 1 plus the length of its rest.
• Example 2: Computing the Sum of a List (my-sum)
  • Step-by-Step Examples:
    • Case 1: my-sum(empty) is 0.
    • Case 2: my-sum([list: 4]) is 4.
    • Case 3: my-sum([list: 4, 7, 9]) is 4 + (sum of [list: 7, 9]), which is 4 + 16 = 20.
  • Discussion:
    • Ask: “What pattern do you see?”
      Answer: For a non-empty list, the sum equals the first element plus the sum of the rest.
• Example 3: Transforming a List by Doubling Each Element (my-doubles)
  • Step-by-Step Examples:
    • Case 1: my-doubles(empty) is empty.
    • Case 2: my-doubles([list: 3]) is [list: 6].
    • Case 3: my-doubles([list: 3, 5, 2]) is:
      • First element: 3 doubled is 6.
      • The rest: my-doubles([list: 5, 2]) is [list: 10, 4].
      • So overall: [list: 6, 10, 4].
  • Activity:
    • Ask students to write down similar examples for a function that returns the string length for each string in a list (e.g., my-str-len).
• Concluding Discussion:
  • Emphasize that these examples demonstrate how the answer for a whole list can be expressed in terms of the first element and the answer for the rest.
  • Explain that this is the key insight that leads to a recursive definition.

---

3. From Examples to Code (15 minutes)

• Recap of the Pattern:
  • If the list is empty, return the “base case” value (e.g., 0 for length or sum, empty for transformation functions).
  • If the list is non-empty (using cases (List) l:), then bind the first element to a variable (say, f) and the rest of the list to another variable (say, r), then compute the result using f and the recursive call on r.
• Writing the Code for my-len:

  fun my-len(l :: List<Any>) -> Number:
    cases (List) l:
      | empty => 0
      | link(f, r) => 1 + my-len(r)
    end
  end
• Writing the Code for my-sum:

  fun my-sum(l :: List<Number>) -> Number:
    cases (List) l:
      | empty => 0
      | link(f, r) => f + my-sum(r)
    end
  end
• Interactive Exercise:
  • Ask students: “Using the same idea, how would you write a recursive function that doubles each element (i.e., my-doubles)?”
  • Guide them to produce:

    fun my-doubles(l :: List<Number>) -> List<Number>:
      cases (List) l:
        | empty => empty
        | link(f, r) => link(f * 2, my-doubles(r))
      end
    end

---

4. Wrap-Up (10 minutes)

• Summary:
  • Emphasize that by examining concrete examples (including the empty case and various non-empty cases), we can “discover” a recursive definition.
  • Highlight that lists are structured data: every non-empty list consists of a first element and a rest (which is itself a list).