Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
recursion recitation notes
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 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 (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)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 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 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment