CSC 324, Summer 2001

Tutorial notes for week 4

This tutorial emphasizes recursion (cdr recursion and car-cdr recursion).

****************************************************************


1. Develop a function that takes an integer parameter n and computes
n! (ie, factorial of n).


ANS:  (define (factorial n)
        (if (<= n 1)
            1
            (* n (factorial (- n 1)))))


****************************************************************

2. a.  Given a list of numbers, returns the sum of all the numbers in the
list.

ANS:

 (define (sum-list l)   
  (cond ((null? l) 0)
        (else (+ (car l) (sum-list (cdr l))))
  )
 )



b. Develop a function that takes a list of numbers and computes the sum of
all even numbers in the list. 

        
ANS:  (define (even? n) (= 0 (modulo n 2)))
;;; Note: there is a built-in function even?

;;; We can use cond or if (cond recommended).

  (define (sum-list-even l)
     (cond ((null? l) 0)
           ((even? (car l)) (+ (car l) (sum-list-even (cdr l))))
           (else (sum-list-even (cdr l)))
    )
  )

  (define (sum-list-even1 l)
    (if (null? l) 
            0
           (if (even? (car l)) (+ (car l) (sum-list-even1 (cdr l)))
                               (sum-list-even1 (cdr l)))
    )
  )      
   

c. Define a function which adds all the numbers in a nested list, on all
levels. Assume there are only numbers in the list.

  (define (sum-all-levels l)
           (cond ((null? l) 0)
               ((atom? (car  l)) (+ (car l) (sum-all-levels (cdr l))))
               (else (+ (sum-all-levels (car l))
                        (sum-all-levels (cdr l))))
           )
  )  
 
;;; This is a helper function discussed in lecture
(define (atom? x) (not (pair? x)))


****************************************************************

3.a. In the next functions, e is an atom and lst is a non-nested list.

(member e lst) => returns #t if e is in lst, #f/() otherwise.

(define (member e lst)
  (cond ((null? lst) #f)
        ((eq? e (car lst)) #t)
        (else (member e (cdr lst)))
  )
)


Note: There is a built-in member, which returns #f/() in the
element is not in list. If the element was found it returns the rest of
the list starting with that element.

 b. In the next function, e is an atom and lst is a nested list.

(nested_member e lst)
 => returns #t if e is in lst on any level, #f/() otherwise.

(define (nested_member e lst)
  (cond ((null? lst) #f)
        ((eq? e (car lst)) #t)  
        ((not (list? (car lst))) (nested_member e (cdr lst)))
        (else (or (nested_member e (car lst))
                  (nested_member e (cdr lst))))
  )
)  

****************************************************************

4. Questions about H2.

5.  Substitute an element with another element in a list, at the surface
level, and then at all levels. 

(define (subst el new_el lst)
 (cond ((null? lst) ())
       ((eq? el (car lst)) (cons new_el (subst el new_el (cdr lst))))
       (else (cons (car lst) (subst el new_el (cdr lst))))
 )
)

(define (subst_all_levels el new_el lst)
 (cond ((null? lst) ())
       ((pair? (car lst))
          (cons (subst_all_levels el new_el (car lst))
                (subst_all_levels el new_el (cdr lst))))
       ((eq? el (car lst))
           (cons new_el (subst_all_levels el new_el (cdr lst))))
       (else (cons (car lst) (subst_all_levels el new_el (cdr lst))))
 )
)