recursion recitation notes

how-cons-works.rkt

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; NOTE: This particular week's examples are much easier to read in DrRacket,
; since they make heavy use of the comment box. Would recommend downloading
; the .rkt files off the website and viewing them on your own computer.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;
; how cons works
;;;;;;;;;;;;;;;;;;;;;;;;;;

(define LIST (list 1 2 3))

; (list 1 2 3 empty)

(first LIST)  ; 1
(rest LIST)  ; (list 2 3)

; (cons (first LIST)
;       (rest LIST))


(check-expect
 (cons 1
       ; (list 2 3)
       (cons 2
             ; (list 3)
             (cons 3
                   empty)))
 (list 1 2 3))

iterative-recursion.rkt

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Iterative Recursion (recursion with accumulators)
; 
; IDEAS:
; 1. Use accumulators to avoid leaving a long recursive trail
; 2. Use local to package your iterative recursive functions nicely
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; ; Remember that the (recursive-sum) function above will look like this
; ; before simplification:
; 
; (+ 1 (+ 2 (+ 3 (+ 4 empty))))
; ;^^^^^^^^^^^^^^
; ; we want to avoid this long chain of partial results
; 
; ; IDEA 1: Instead of having to remember the all previous recursive calls,
; ; keep an ACCUMULATOR to flatten all of those partial results
; 
; ; the accumulator is the same idea from foldl:
; (foldl + 0 (list 1 2 3 4))
;        ; ^
;        ; initial accumulator


; iterative-sum-list : listof-numbers, number -> number
; sums the list using iterative recursion (accumulators!)
(define (iterative-sum-list lon partial-sum)
  (if (empty? lon) ; same base case
      partial-sum  ; was 0 before, now we return the partial-sum

      ; notice how the recursive call wraps the entire "else" case
      ; there's no (+ 1 ...) trail to leave behind
      (iterative-sum-list (rest lon)
                          (+ (first lon) partial-sum))))

(iterative-sum-list (list 1 2 3 4 5 6 7 8)
                 0)
               ; ^
               ; remember, we need to specify the start value of
               ; the accumulator, just like with foldl

; but that's kind of annoying.....

; IDEA 2: Use local to write a wrapper around our new
; iterative recursive function, in order to eliminate
; the need for the user to specify the start value

; better-sum-list : listof-numbers -> number
; sums the list using iterative recursion, and NO extra '0' input
(define (better-sum-list lon)
  (local [; I just copy-pasted iterative-sum-list here...
          (define (iterative-sum-list lon partial-sum)
            (if (empty? lon) ; same base case
                partial-sum  ; was 0 before, now we return the partial-sum
                (iterative-sum-list (rest lon)
                                    (+ (first lon) partial-sum))))]
    ; In the body of the local, make the "starting call" with the 0 value
    (sum-list-helper lon 0)))

; GENERAL PROCESS: writing a wrapper over an iterative recursive function

; Step 1 - write the wrapper's signature and stub out the function
; typically you want to eliminate the accumulator input

; ; better-sum-list : listof-numbers -> number
; (define (better-sum-list better-lon)
;   ...)


; Step 2 - add a local

; ; better-sum-list : listof-numbers -> number
; (define (better-sum-list better-lon)
;   (local [...your old function will go here...]
;     
;     ...you'll call your old function here...)


; Step 2.5 - copy your old function inside the square brackets

; ; better-sum-list : listof-numbers -> number
; (define (better-sum-list better-lon)
;   (local [(define (iterative-sum-list lon partial-sum)
;             (if (empty? lon) ; same base case
;                 partial-sum  ; was 0 before, now we return the partial-sum
;                 (iterative-sum-list (rest lon)
;                                     (+ (first lon) partial-sum))))]
;     
;     ...you'll call your old function here...)


; 3 - In the body of your local, add the "kickoff" call to your old function,
; which you've defined locally in the square brackets

; ; better-sum-list : listof-numbers -> number
; (define (better-sum-list better-lon)
;   (local [(define (iterative-sum-list lon partial-sum)
;             (if (empty? lon) ; same base case
;                 partial-sum  ; was 0 before, now we return the partial-sum
;                 (iterative-sum-list (rest lon)
;                                     (+ (first lon) partial-sum))))]
; 
;     ; notice we pass in two arguments:
;     ; - the list input provided to the wrapper function
;     ; - the starting accumulator, which we know is always 0
;     (iterative-sum-list better-lon 0)))

map-filter.rkt

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Using regular (non-iterative) recursion to implement
; map and filter
;
; IDEAS:
; 1. pick a sample input
; 2. figure out what the output looks like
; 3. figure out what the output looks like before it's simplified
; 4. try to notice the recursive pattern
; 5. Now write a function to build up that thing, recursively
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; HOW A MAP IS BORN
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; map : proc        lst       -> lst
;       (A -> B)    (listof A)   (listof B)

; IDEA 1: Pick inputs

; thanks-obama : string -> string
; demo proc
(define (thanks-obama s)
  (string-append "Thanks Obama for " s))

; demo lst
(define list-of-great-things
  (list "hoverboards" "Fall Out Boy"))

; ; IDEA 2-4: Using the above inputs, our output will look like this:
; 
; (cons (thanks-obama "hoverboards")
;       (cons (thanks-obama "Fall Out Boy")
;             empty))
; 
; ; Need to write a function that makes something like this.


; my-map : (A -> B), (listof A) -> (listof B)
; NOT with iterative recursion/accumulators
(define (my-map proc lst)
  (if (empty? lst)
      empty
      ; Recursive step
      (cons (proc (first lst))
            (my-map proc (rest lst)))))

; (my-map thanks-obama list-of-great-things)
; 
; ; expand list-of-great-things
; (my-map thanks-obama
;         (list "hoverboards" "Fall Out Boy"))
; 
; ; expand my-map
; (cons (thanks-obama "hoverboards")
;       (my-map thanks-obama (list "Fall Out Boy")))
; 
; ; expand recursive call
; (cons "Thanks Obama for hoverboards"
;       (cons "Thanks Obama for Fall Out Boy"
;             empty))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; HOW A FILTER IS BORN
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; filter : pred        lst       -> lst
;          (A -> bool) (listof A)   (listof A)

; my-filter : (A -> boolean), (listof A) -> (listof A)
; NOT with iterative recursion/accumulators
(define (my-filter pred lst)
  (if (empty? lst)
      empty
      
      (if
       ; test the first item in the list
       (pred (first lst))
       ; if it passes, then cons first item
       (cons (first lst)
             (my-filter pred (rest lst)))
       ; else just skip first item
       (my-filter pred (rest lst)))))

; EXAMPLE: Calling my-filter with an inline lambda, which checks
; if a number is over 9000

(my-filter
 ; number -> number
 ; checks if a number is over 9000
 (lambda (n) (> n 9000))
 (list 0 1 2 9001))

; this will return (list 9001)

recursion-general.rkt

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Recursion (general type)
; 
; IDEAS:
; 1. We use recursion to work with recursively-defined data
; 2. then I give you some example templates idk
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; IDEA 1: Recursive data definitions
; (remember that in English, a "recursive definition"
; is using a word in its own definition)

; A Number is one of
; - 0
; - (+ 1 Number)

; A Listof-String is one of
; - empty
; - (cons String Listof-String)

; (cons 5 empty)
; (cons 6 (cons 5 empty))


; ; A template for general recursion
; (define recursive-<fn>
;   (lambda (x)
;     (if <Base Case>
;         <Base Case Result>
;         ; if not base case, then Recursive Step
;         (<Combiner>
;          ...current value...
;          (recursive-<fn> ...next value...)))))


; ; A template for number recursion
; (define recursive-number-<fn>
;   (lambda (n)
;     (if
;      ; Base Case: n = 0
;      (= n 0)
;      ; Base Case Result: usually either 0 or 1
;      0
;      ; Recursive Step
;      (<fn>
;       ...n...
;       (recursive-number-<fn> (- n 1))))))


; ; A template for list recursion
; (define recursive-list-<fn>
;   (lambda (lst)
;     (if
;      ; Base Case: empty list
;      (empty? lst)
;      ; Base Case Result: usually either 0 or 1
;      0
;      ; Recursive Step
;      (<fn>
;       ...(first lst)...
;       (recursive-list-<fn> (rest lst))))))


; recursive-sum : Listof-Numbers -> number
; returns the sum of all the elements in the list
(define (recursive-sum lon)
  (if (empty? lon)
      0
      ; Recursive step
      (+ (first lon)                     ; (combiner (first lon)
         (recursive-sum (rest lon))))))  ;   (recursive-fn (rest lon)))

(recursive-sum (list 1 2 3 4))