;;; CSE 341 - Winter 2010
;;; Scheme recursion examples
;;;
;;; Recursive functions in Scheme usually follow one of a small number of patterns -- so it's
;;; useful to understand these patterns and to know when to use them.
;; List-to-list functions. These take a list and return a new list of the same length.
;; Example: negate every number in a list
(define (negate-each s)
(if (null? s)
()
(cons (- (car s)) (negate-each (cdr s)))))
;; You should know how to write such functions recursively, but they are usually better written
;; using 'map':
(define (map-negate-each s)
(map (lambda (x) (- x)) s))
;; the base case doesn't always need to return ()
;; Example: append
(define (my-append x y)
(if (null? x)
y
(cons (car x) (my-append (cdr x) y))))
;; Mini-exercise
;; Draw a box-and-arrow diagram of the resulting list structures after evaluating these definitions:
;; (define a '(1 2))
;; (define b '(100 200 300))
;; (define c (my-append a b))
;;
;; What is the value of these expressions?
;; (eq? (cddr c) b)
;; (eq? (cdddr c) (cdr b))
;; (eq? c a)
;; (eq? c '(1 2 100 200 300))
;; (equal? c '(1 2 100 200 300))
;;
;; and a messier example:
;; (define d '( (1 2) (3 4) ))
;; (define f (my-append d b))
;; What is the value of these expressions?
;; (eq? (car d) (car f))
;; (eq? (cadr d) (cadr f))
;; map itself is a function of this form (albeit a higher-order one):
(define (my-map f s)
(if (null? s)
()
(cons (f (car s)) (my-map f (cdr s)))))
;; Note: the builtin function 'map' in Scheme is more general, in that it can deal with
;; functions of multiple arguments, e.g.
;; (map + '(1 2) '(10 11))
;; Accumulating functions. These recurse through a list, somehow accumulating the result.
;; Example: sum
(define (sum s)
(if (null? s)
0
(+ (car s) (sum (cdr s)))))
;; tail recursive version:
(define (sum-tr s)
(sum-helper s 0))
(define (sum-helper s partial-sum)
(if (null? s)
partial-sum
(sum-helper (cdr s) (+ (car s) partial-sum))))
;; Also see the "Scheme basics" lecture notes about tail recursion.
;; searches
(define (my-member e x)
(cond ((null? x) #f)
((equal? e (car x)) #t)
(else (my-member e (cdr x)))))
;; Filtering. This is like the list-to-list functions, except that you don't always use the value.
(define (positive-numbers x)
(cond ((null? x) '())
((> (car x) 0) (cons (car x) (positive-numbers (cdr x))))
(else (positive-numbers (cdr x)))))
;; The above funtion is better written using Scheme's 'filter' function:
(define (positive-numbers-with-filter x)
(filter (lambda (n) (> n 0)) x))
;; Mini-exercise. Define your own filter function, called 'my-filter'
;; double recursions (on both the car and cdr of a list)
(define (sum-all s)
(cond ((null? s) 0)
((number? s) s)
((pair? s) (+ (sum-all (car s)) (sum-all (cdr s))))
(else (error "non-numeric value in the list"))))