Data Directed Design

#Enum data

#Union data

#Self Referential Data(Recursion)

Trippy I know.

#The two main things you need to focus on are:

1. Base case: what we do when the list is empty, aka the termination condition

2. How to contribute/combine to the base case

   Focus on the 1 list long case and how you combine it with the base case to achieve the intended purpose, and trust that it will just work for a list of any length

#Self reference template

; ListOfNumbers is one of:
; - empty
; - (cons Number ListOfNumber)
; interp. a list of numbers

; examples:
(define one-ls (cons 99 empty))
(define two-ls (cons 4 (cons 6 empty)))
(define three-ls (cons 1 (cons 8 (cons 5 empty))))

(define (list-of-nums-temp lst)
  (cond [(empty? lst) ...] ; ◄────── (1) ... base case
        [else
         (... (first lst)
              (list-temp (rest lst)))]))
        ; ▲
        ; │
        ; │
        ; (2) ... contribution to the base

Notice how the Data Definition maps to the code. It’s a one of, so we need a cond with two matching cases. In the 2nd case, we simplify what would be (cons? lst) to else instead for short. Always use the derived template as starter code, as all recursive functions will have this structure.

#Recursion Exercise

Use the design recipe and recursive template to work through the following 3 problems
sum-price , count-items , has-peanuts?

; ListOfNumber is one of:
; - empty
; - (cons Number ListOfNumber)
; interp. a sequence of numbers
; TODO: TEMPLATE

; sum-prices : (ListOfNumber -> Number)
; produces the sum total of the numbers in the given list

; count-items: (ListOfNumber -> Number)
; produces the amount of numbers in the given list

; ListOfString is one of:
; - empty
;- (cons String ListOfString)
; interp. a sequnce of strings
; TODO: TEMPLATE

; has-peanuts? : (ListOfString -> Boolean)
; produces #true if the list contains "peanuts"

; Notice the similarities between 3 recursive functions

; ListOfNumber is one of:
; - empty
; - (cons Number ListOfNumber)
; interp. a sequence of numbers
(define (list-num-temp num-ls)
  (cond
    [(empty? num-ls) ...]
    [else
     (... (first num-ls)
          (list-num-temp (rest num-ls)))]))

; sum-prices : (ListOfNumber -> Number)
; produces the sum total of the numbers in the given list
(check-expect (sum-prices empty) 0)
(check-expect (sum-prices (cons 0.50 (cons 4 empty))) (+ 4 0.50))
(check-expect (sum-prices (cons 4 (cons 1 (cons 7 empty)))) (+ 4 1 7))
(define (sum-prices num-lst)
  (cond
    [(empty? num-lst) 0]
    [else
     (+  (first num-lst)
         (sum-prices (rest num-lst)))]))

; count-items: (ListOfNumber -> Number)
; produces the amount of numbers in the given list
(check-expect (count-items empty) 0)
(check-expect (count-items (cons 33 (cons 4 empty))) 2)
(define (count-items num-lst)
  (cond
    [(empty? num-lst) 0]
    [else
     (+ 1
        (count-items (rest num-lst)))]))

; ListOfString is one of:
; - empty
; - (cons String ListOfString)
; interp. a sequnce of strings
(define (list-string-temp str-ls)
  (cond
    [(empty? str-ls) ...]
    [else
     (... (first str-ls)
          (list-string-temp (rest str-ls)))]))

; has-peanuts? : (ListOfString -> Boolean)
; produces #true if the list contains "peanuts"
(check-expect (has-peanuts? empty) #false)
(check-expect (has-peanuts? (cons "vanilla" (cons "chocolate" empty))) #true)
(check-expect (has-peanuts? (cons "mint" (cons "peanuts" empty))) #true)
(define (has-peanuts? str-lst)
  (cond
    [(empty? str-lst) #false]
    [else
     (if (string=? (first str-lst) "peanuts")
         #true
         (has-peanuts? (rest str-lst)))]))

#Similarities

Here’s a table in the main ways they are similar but differ:

#How does it work?

The individual/micro/mechanical operations of recursive functions expliots the rule that we’ve learned all the way in the start of the course, and that is that function operands(aka parameters, inputs, arguments) need to be values before the operator can do its job. Let’s explore this in a bit more detail!

Use the stepper and step through this expression:

(+ (* 2 6 (/ 4 4)) (- 1 1))

This is the order of calls:
Calling:
+ is called 1st
* is called 2nd
/ is called 3rd
- is called last

Even though + is called first, it has to wait until all of its operands resolve into values, so it is executed last. The order of the operations that executes is different:

Executing:
/ is executed 1st
* is executed 2nd
- is executed 3rd
+ is executed last

#Table method

It is often better to write out the execution in a table format for more of a birds eye view. Here is the execution of sum-prices when it is given the list (cons 4 (cons 1 (cons 7 empty))):

Notice that the list gets smaller on each iteration step

#Top mistakes students make when doing recursion

1. Being hung up on the individual mechanical operations of each recursive call
2. Not writing or using a template as a starter
3. Not using the stepper/writing things down in a table
4. Not having a clear purpose statement and trusting it, and focusing too much on the code. Purpose statements should focus on what the function computes not how it goes about it
5. Forgetting to make sure the a recursive function calls itself
6. Not having a good base case
7. Not having the functions follow the signature

#Debugging recursive functions

1. Comment out all tests except the failing one, and use the stepper
2. Write out in a table the first and rest of every call to get a birds eyeview: beginning student tables

#Why is recursion hard?

1. Default mindset: Humans think sequentially (“do A, then B, then C”).

Recursion demands: “Solve a smaller version of the problem first, then combine results”—a backwards or self-referential logic.

Example:

Iterative: “To climb 10 stairs, step 1, then 2, then 3...”

Recursive: “To climb 10 stairs, first know how to climb 9 stairs, then add one more step.”

Why it feels unnatural: Recursion asks us to delegate the work before seeing the result, which feels like “cheating”, compared to the iteration where we can see all the previous steps before us more easily.

2. The Fear of the Unknown

Desire for control: People want to trace every call to feel “sure” it works.

Recursion’s opacity: Each recursive call hides complexity, creating unease.

3. Infinite Loop Anxiety

Base-case paranoia: Missing or incorrect base cases lead to infinite recursion (and stack overflows). In contrast to iteration, we have a more intuitive grasp at when we end up front with very little chances of infinite looping.

The idea of why recursion works is similar to proofs by mathematical induction.