; recursive-fns.scm

; 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)