Warning! You are being recorded (and transcribed) (provided the technology is working correctly).
Approximate overview
I’d like to see some you do a more in-depth brain dump. Putting
information in a “usable form” helps train your brain. For example,
what does an if expression look like? How many parameters does
string-append have? What are the key operations for lists and
what are examples of their use?
We may try a quick bit of practice.
Academic/Scholarly
Cultural
Peer
Wellness
Misc
CHANGES.rkt file.CHANGES.rkt file.In the following, the definition of sum includes sum, which we are
trying to define. Is this really possible and, if so, how is it possible?
(define sum
(lambda (numbers)
(if (null? numbers)
0
(+ (car numbers) (sum (cdr numbers))))))
Welcome to the magic of recursion, in which we build procedures using the procedure we are building as a helper.
Yes, it is possible. It’s possible, in part, because of what our mental model demonstrates: These self-referential definitions naturally expand and then give us an answer.
Reminder: (if #f CONSEQUENT ALTERNATE) --> ALTERNATE
(if (null? numbers) 0 (+ (car numbers) (sum (cdr numbers))))))
(sum (list 4 5 2))
--> (if (null? (list 4 5 2)) 0 (+ (car (list 4 5 2)) (sum (cdr (list 4 5 2)))))
--> (if #f 0 (+ (car (list 4 5 2)) (sum (cdr (list 4 5 2)))))
--> (+ (car (list 4 5 2)) (sum (cdr (list 4 5 2))))
--> (+ 4 (sum (cdr (list 4 5 2))))
--> (+ 4 (sum (list 5 2)))
--> (+ 4 (if (null? (list 5 2)) 0 (+ (car (list 5 2)) (sum (cdr (list 5 2))))))
--> (+ 4 (if (null? (list 5 2)) 0 (+ (car (list 5 2)) (sum (cdr (list 5 2))))))
--> (+ 4 (if #f 0 (+ (car (list 5 2)) (sum (cdr (list 5 2))))))
--> (+ 4 (+ (car (list 5 2)) (sum (cdr (list 5 2)))))
--> (+ 4 (+ 5 (sum (cdr (list 5 2)))))
--> (+ 4 (+ 5 (sum (list 2))))
--> (+ 4 (+ 5 (if (null? (list 2)) 0 (+ (car (list 2)) (sum (cdr (list 2)))))))
--> (+ 4 (+ 5 (if #f 0 (+ (car (list 2)) (sum (cdr (list 2)))))))
--> (+ 4 (+ 5 (+ (car (list 2)) (sum (cdr (list 2))))))
--> (+ 4 (+ 5 (+ 2 (sum (cdr (list 2))))))
--> (+ 4 (+ 5 (+ 2 (sum null))))
--> (+ 4 (+ 5 (+ 2 (if (null? null) 0 (+ (car null) (sum (cdr null)))))))
--> (+ 4 (+ 5 (+ 2 (if #t 0 (+ (car null) (sum (cdr null)))))))
--> (+ 4 (+ 5 (+ 2 0)))
--> (+ 4 (+ 5 2))
--> (+ 4 7)
--> 11
(define solid-square
(lambda (size color)
(solid-square size color)))
(solid-square 12 "blue")
--> (solid-square 12 "blue")
--> (solid-square 12 "blue")
--> (solid-square 12 "blue")
--> (solid-square 12 "blue")
--> (solid-square 12 "blue")
--> (solid-square 12 "blue")
Whoops!
In Racket, the behavior we’ll see is that we never ever get a prompt in the interactions pane.
It’s time to return to something we covered early in the semester.
Six key components to algorithm writing:
TPS: What do we know about each of these in Scheme?
append, cons, car, cdr, index-of, list-ref)string-append, substring)+, /)char->integer)rectangle, rotate, hflip)lambdacutodefine)(if TEST CONSEQUENT ALTERNATE)(cond [GUARD1 CONSEQUENT1] [GUARD2 CONSEQUENT2] ... [ELSE ALTERNATE])(cond [GUARD1 CONSEQUENT1a CONSEQUENT1b] [GUARD2 CONSEQUENT2] ... [ELSE ALTERNATE])or and and can provide some measure of conditional control.map - Does something repeatedly (once to each element of a list)reduce - does something repeatedly (merges neighboring elements)filterpixel-map - applies a procedure to each pixelmake-list.defineThe weird part of recursion is that we are solving the “smaller” problem with exactly the same solution as the smaller problem; we have to assume we’ve written something we haven’t written yet.
The magic recursion fairy makes it work.
We’re going to rephrase recursion in terms of “delegation”. When given a large problem, an executive will normally delegate most of the problem to an assistant. We’ll assume that their assistant will do the same.
To count the cards in a list
To count the number of odd numbers in a list
To sort a list of cards
;;; (list-length lst) -> integer?
;;; lst : list?
;;; Define how many elements there are in a list.
(define list-length
(lambda (lst)
(if (null? lst)
0
(+ 1 (list-length (cdr lst))))))
Yay! It works!
;;; (tally-odds lst) -> integer?
;;; lst : (list-of integer?)
;;; Count how many odd numbers appear in `lst`.
(define tally-odds
(lambda (lst)
(if (null? lst)
0
(+ (if (odd? (car lst)) 1 0)
(tally-odds (cdr lst))))))
(define tally-odds
(lambda (lst)
(cond
[(null? lst)
0]
[(odd? (car lst))
(+ 1 (tally-odds (cdr lst)))]
[else
(tally-odds (cdr lst))])))
(define tally-odds
(lambda (lst)
(list-length (filter odd? lst))))
; Correct; doesn't help us learn recursion
;;; (insert-number num sorted-nums) -> (list-of integer?)
;;; num : integer?
;;; sorted-nums : (all-of list-of-integer? sorted?)
;;; Insert `num` into the correct place in `sorted-nums`
;;;
;;; Notes: Look at each element in turn. If you're bigger, skip over
;;; it. If you're smaller, insert it there. If there are no elements,
;;; inserting it means "create a new list".
(define insert-number
(lambda (num sorted-nums)
(cond
[(null? sorted-nums)
(list num)]
[(<= num (car sorted-nums))
(cons num sorted-nums)]
[else
(cons (car sorted-nums)
(insert-number num (cdr sorted-nums)))])))
;;; (sort-nums nums) -> (all-of (list-of integer?) sorted?)
;;; nums : (list-of integer?)
;;; Sort `nums` in increasing order.
(define sort-nums
(lambda (nums)
(if (null? nums)
null
(insert-number (car nums)
(sort-nums (cdr nums))))))