CSC151 2009F, Class 26: Recursion Basics
Admin:
* Work with whomever you'd like to work with
* Are there questions on Assignment 6?
* One question on atan when x is 0
* What about radial colors? Use the radius!
* Why are we subtracting x-center and y-center? Because it puts
the origin in th emiddle
* Why can't you type correctly8? Because
* While the outlines imply that we discussed recursion on Friday,
we clearly did not.
* I'm keeping them this way for my convenience
* I told you I would not give any writeups for this week.
However, you would see some learning benefit from finishing today's lab.
* I'm not feeling great, and probably won't be around this afternoon.
* Quiz 6 returned: We'll go over it quickly
* Problem two: Write (first-two lst) that returns the first two components
of a list, as a list.
* null - List with no elements (the empty list)
* cons - (cons a L) => makes new list by adding a to the front of L
* car - Gives you the first element of a list
* cdr - Gives you the list without the first value
* Subproblem: Build a list of two elements. Try the list (1 2)
(cons 1 (cons 2 null))
* Subproblem: First element of the list, lst
(car lst)
* Subproblem: Second element of a list
(car (cdr lst))
* Put the subproblems together
(cons (car lst) (cons (car (cdr lst)) null))
Overview:
* Going over quiz 6
* Repetition, revisited
* The idea of recursion.
* A sample recursive procedure: sum.
* Time for lab.
Repetition: One of the key building blocks of algorithms
* Repeat with for-each
* Apply a procedure to each element of a list of things, in succession
* Returning *nothing*
* Repeat with repeat
* Repeat a procedure a specified number of times
* Returning *nothing*
* Repeat with map
* Apply a procedure to each element of a list of things
* Returning the list of the results of each application
* There are many times we want to repeat, but not in any of these models
* Sum the elements in a list
* Extract the elements in a list that meet some criteria
* ...
* What do we do?
* Enter recursion: Scheme's general repetition mechanism
* A lot like induction
Recursion
* To solve a big problem, solve smaller problems
* Strange aspect in recursion: You solve the smaller problem *with the
same algorithm*
* Except when the problem is small enough, then you solve it directly
* Detour to Scheme: We develop Sum
(define sum
(lambda (lst)
; If the list has one element
(if (null? (cdr lst))
; Return that element
(car lst)
; Otherwise, do something tricky
(+ (car lst) (sum (cdr lst))))))
How does sum do its computation
* (sum (list 1 2 3))
=> (if (null? (cdr (list 1 2 3)))
; Return that element
(car (list 1 2 3))
(+ (car (list 1 2 3)) (sum (cdr (list 1 2 3)))))))
TEST DOES NOT HOLD
=> (+ (car (list 1 2 3)) (sum (cdr (list 1 2 3))))
=> (+ 1 (sum (cdr (list 1 2 3))))
=> (+ 1 (sum (list 2 3)))
=> (+ 1 (if (null? (cdr (list 2 3)))
; Return that element
(car (list 2 3))
(+ (car (list 2 3)) (sum (cdr (list 2 3)))))))
TEST DOES NOT HOLD
=> (+ 1 (+ 2 (sum (cdr (list 2 3)))))
=> (+ 1 (+ 2 (sum (list 3))))
=> (+ 1 (+ 2 (if (null? (cdr (list 3)))
; Return that element
(car (list 3))
(+ (car (list 3)) (sum (cdr (list 3)))))))
TEST HOLDS
=> (+ 1 (+ 2 (car (list 3))))
=> (+ 1 (+ 2 3))
=> (+ 1 5)
=> 6