CprS376 Schedule
CprS376 Class 2
CprS376 Class 4

Procedures and the Processes They Generate

Class 3 - Section 1.2



Contents

Everybody's Favorite Recursive Function, fact, and Its Iterative Cousin, fact-iter
; fact.ss
; SICP section 1.2.1
; Chris Parrish

; a recursive process

(define fact
  (lambda (n)
    (if (zero? n)
      1
      (* n (fact (sub1 n))))))

(trace fact)

(fact 120)

; an iterative process

(define fact
  (lambda (n)
    (fact-iter 1 n 1)))

(define fact-iter
  (lambda (k n ans)
    (if (> k n)
      ans
      (fact-iter (add1 k) n (* k ans)))))

(trace fact-iter)

(fact 120)

The Fibonacci Function Generates a More Elaborate Recursion
; fib.ss
; SICP section 1.2.2
; Chris Parrish

; tree recursion

(define fib
  (lambda (n)
    (cond ((= 0 n) 0)
          ((= 1 n) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2)))))))
(trace fib)

(fib 5)

; cf. SICP fig. 1.5, page 38

Primality Testing, a la SICP

;; primes.ss

;; primality testing
;; SICP section 1.2.6
;; source code from "ch1.scm"

;;;SECTION 1.2.6

;; prime?

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define square     ;; added by Chris Parrish
  (lambda (x)
    (* x x)))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))


;; fast-prime?

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))        

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))


;;EXERCISE 1.22
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

A Medley of Recursive Functions

; recursive-fns.ss

; Elementary Recursion in Scheme

; -------------------------------------------------------------------------

; FACTORIAL

; This example uses simple recursion to calculate the factorial of a number.
; The terminating condition occurs when the number is 0. The value of the function at 0 is 1.
; The recursive relation is the fact that the factorial of n can be obtained from the factorial
; of  n-1 by multiplying by n, i.e., fact(n) = n * fact(n-1).

(define fact 
  (lambda (num)
    (if (zero? num)
        1
        (* num (fact (sub1 num))))))

(fact 5)

; -------------------------------------------------------------------------

; LIST-SUM

; sum the elements in a list of numbers

(define list-sum 
  (lambda (lis)
    (if (null? lis)
        0
        (+ (car lis) 
           (list-sum (cdr lis))))))

(list-sum '(2 4 23 12 -4 7))
(list-sum '(2))
(list-sum '())

; -------------------------------------------------------------------------

; LISTNUMS

; This is a simple recursive function that generates a list of the numbers from n to 1.
; The terminating condition occurs when n is 0. The recursive relation is the fact that
; listnums n =  n + listnums (n-1).

(define listnums
  (lambda (n)
    (if (zero? n)
        '()
        (cons n (listnums (sub1 n))))))

(listnums 6)

; -------------------------------------------------------------------------

; NEGNUMS

; This recursive function goes through a list 
; and picks out all its negative numbers.

(define negnums 
  (lambda (theList)
    (cond ((null? theList) '())
          ((negnum? (car theList)) (cons (car theList) 
                                         (negnums (cdr theList))))
          (else (negnums (cdr theList))))))

(define negnum?
  (lambda (n)
    (and (number? n)
         (> 0 n))))

(negnums '(3 -5 a 12 -4))

; -------------------------------------------------------------------------

; LISTLENGTH

; This is a recursive function that counts the number of elements in a list.
; An empty list terminates the recursion.

(define list-length 
  (lambda (theList)
    (if (null? theList)
        0
        (add1 (list-length (cdr theList))))))

(list-length '(a b c d e f))
(list-length '(1 2 3))

; -------------------------------------------------------------------------

;INTERSECTON

; Compute the intersection of two lists

(define my-intersection 
  (lambda (listA listB)
    (cond
     ((null? listA)
      '())
     ((member (car listA) listB)
      (cons (car listA) 
            (my-intersection (cdr listA) listB)))
     (else (my-intersection (cdr listA) listB)))))

(my-intersection '(hola que tal) '(que hay))
(my-intersection '(buenos dias) '(como esta))
(my-intersection '(buenos dias como esta) '(como esta dias))

; -------------------------------------------------------------------------

; MERGE.LSP

; Merge two ordered lists into a single ordered list
; Use trace to follow the action

(define my-merge 
  (lambda (listA listB)
    (cond
     ((null? listA) listB)
     ((null? listB) listA)
     ((<= (car listA) (car listB))
      (my-merge (cdr listA) 
                (cons (car listA) listB)))
     (else (cons (car listB) 
                 (my-merge listA (cdr listB)))))))

(my-merge '(1 3 5 7 9) '(1 2 4 6))
(my-merge '(1) '(0 2 4 6 8))
(my-merge () '(1 3 5))
(my-merge '(1 2 3) '(1 2 3))
(my-merge () ())

; -------------------------------------------------------------------------

; POWER

; This example uses simple recursion to calculate m to the nth power.
; The zeroth power of anything is 1.
; The nth power of m is obtained from the (n-1)st power by
;                     power(m,n) = m * power(m,n-1).

(define power 
  (lambda (m n)
    (if (zero? n) 
        1
        (* m (power m (- n 1))))))

(trace power)
(power 5 3)

; -------------------------------------------------------------------------

; POWER_SET

; Calculate the power set (set of all subsets) of a given set 

(define powerset 
  (lambda (lst)
    (if (null? lst) 
        '(())
        (append (addto (car lst) (powerset (cdr lst))) 
                (powerset (cdr lst))))))

(define addto 
  (lambda (elt lst)
    (if (null? lst) 
        '()
        (cons (cons elt (car lst)) 
              (addto elt (cdr lst))))))

(powerset '(a b c))

; -------------------------------------------------------------------------

; RECTANGLE

; These functions will print a rectangle with col columns and row rows,
; using the character char.
; Line is a helping function called by rect. Line prints col characters.
; Princ prints the character without a carriage return and line feed. Terpri
; emits the carriage return/line feed only after a whole row has been printed.

(define rect 
  (lambda (col row char)
    (newline)
    (if (zero? row)
        (newline)
        (begin
         (line col char)
         (rect col (sub1 row) char)))))

(define line 
  (lambda (col char)
    (if (zero? col)
        '()
        (begin
         (write char) 
         (line (sub1 col) char)))))


(rect '6 '4 's)

; -------------------------------------------------------------------------

;UNIQUE

; Remove duplicate atoms from a list

(define unique
  (lambda (thisList)
    (cond ((null? thisList) thisList)
          ((member (car thisList) (cdr thisList))
           (unique (cdr thisList)))
          (else (cons (car thisList) (unique (cdr thisList)))))))

(unique '(tea coffee tea milk tea coffee))
(unique '(tea coffee))
(unique ())

; -------------------------------------------------------------------------

; UNION

; This functIon uses "cdr recursion" to find the union of two lists.
; It looks at each element of listA and, if the element is not in listB,
; it will be added to listB.

(define my-union 
  (lambda (listA listB)
    (cond ((null? listA) (unique listB))
          ((member (car listA) listB) (my-union (cdr listA) listB))
          (else (cons (car listA) (my-union (cdr listA) listB))))))

(my-union '(a b c d e) '(b g g g m e))
(my-union '(a m c) '(b m d))
(my-union '(tea coffee) '(jelly beans and peas))
(my-union '(tea jelly) '(tea beans))
(my-union () '(tea))
(my-union '(coffee) ())


; -------------------------------------------------------------------------

; oddEven

; This is a recursive function that creates a list of the numbers
; between 0 and n, placing all the odd numbers at the head of the list,
; and all the even numbers at the end. Zero goes in the middle.

(define oddEven 
  (lambda (n)
    (cond ((zero? n) (list 0))
          ((even? n) (append (oddEven (sub1 n)) (list n)))
          ((odd? n) (cons n (oddEven (sub1 n)))))))
  
(define even?
  (lambda (n)
    (if (zero? n)
        #t
        (odd? (sub1 n)))))
  
(define odd?
  (lambda (n)
    (if (zero? n)
        #f
        (even? (sub1 n)))))

(oddEven 6)

SICP Source Code

Programming Exercises

We will continue to work through the following exercises from chapter 1 in class today: 5, 9, 10, 12,15, 17, 18, 29, 30, 31, 32, 34, 35, 36, 37.