Jump to content

Lisp EN -- Laboratory 3 -- 2006-2007 -- info.uvt.ro

From Wikiversity
Important! These pages are somehow outdated and it is recommended to consult the newer version at Functional programming -- 2008-2009 -- info.uvt.ro (by Ciprian Crăciun).

Lisp EN -- 2006-2007 -- info.uvt.ro


Classes of recursive calls

[edit]

Linear recursion

[edit]

A recursive function is a linear one if it calls it self only once per call.


  • Factorial function:
(defun n! (n)
    (cond
        ((<= n 1) 1)
        (t (* n (n! (1- n))))
    ))

(n! 11) => 39916800


  • Removing all non-number elements from a list:
(defun remove-non-numbers (l)
    (cond
        ((null l) nil)
        ((numberp (car l))
            (cons (car l) (remove-non-numbers (cdr l))))
        (t
            (remove-non-numbers (cdr l)))
    ))

(remove-non-numbers '(1 2 a b 3 4)) => (1 2 3 4)
    • We can observe that there are two recursive calls, but each one in a distinct case, thus it results only (at most) one recursive call per call.


Fat (exponential) recursion

[edit]

A recursive function has a fat behavior if it calls it self two or more times per call.


(defun fibonacci (n)
    (cond
        ((= n 1) 0)
        ((= n 2) 1)
        (t (+ (fibonacci (- n 1)) (fibonacci (- n 2))))
    ))

(fibonacci 1) => 0
(fibonacci 2) => 1
(fibonacci 3) => 1
(fibonacci 4) => 2
(fibonacci 10) => 34
(fibonacci 20) => 4181


(defun ackermann (m n)
    (cond
        ((zerop m) (1+ n))
        ((and (plusp m) (zerop n))
            (ackermann (1- m) 1))
        (t
            (ackermann (1- m) (ackermann m (1- n))))
    ))

(ackermann 3 4) => 125

Tail recursion

[edit]

Tail recursion article on Wikipedia

A tail recursive function is just a linear recursive function in which the last executed operation is the recursive call.

In general most linear recursive functions, and some exponential recursive functions, can be rewritten as tail recursive functions by adding additional accumulator arguments. The new function is an auxiliary function which will be called by a wrapping function with the default values for the accumulator arguments.


  • Factorial -- tail recursive
(defun n!-a (n a)
    (cond
        ((zerop n) a)
        (t (n!-a (1- n) (* a n)))
    ))

(defun n! (n)
    (n!-a n 1))

(n! 5) => 120
(n! 10) => 3628800


  • Fibonacci function -- tail recursive
(defun fibonacci-a (n a1 a2)
    (cond
        ((<= n 1) a1)
        (t (fibonacci-a (1- n) a2 (+ a1 a2)))
    ))

(defun fibonacci (n)
    (fibonacci-a n 0 1))

(fibonacci 1) => 0
(fibonacci 2) => 1
(fibonacci 3) => 2
(fibonacci 4) => 3
(fibonacci 10) => 34
(fibonacci 100) => 218922995834555169026


  • Reversing a list
(defun my-reverse-a (l r)
    (cond
        ((null l) r)
        (t (my-reverse-a (cdr l) (cons (car l) r)))
    ))

(defun my-reverse (l)
    (my-reverse-a l nil))

(my-reverse '(1 2 3 4)) => (4 3 2 1)


  • Cloning a list
(defun my-clone-a (l r)
    (cond
        ((null l) r)
        (t (my-clone-a (cdr l) (append r (list (car l)))))
    ))

(defun my-clone (l)
    (my-clone-a l nil))

(my-clone '(1 2 3 4 5))
    • As we can see the my-clone function can be written as a final recursive function, but it's best to leave it as a linear one.


Shallow and deep recursion

[edit]

These concepts apply to list (or different data-structure) processing functions.

A shallow function is a function which takes into account only the given list, ignoring any contained lists.


  • Count atoms -- shallow
(defun count-atoms-shallow (l)
    (cond
        ((null l) 0)
        ((atom (car l))
            (1+ (count-atoms-shallow (cdr l))))
        (t
            (count-atoms-shallow (cdr l)))
    ))

(count-atoms-shallow '(1 2 (3 4 5) 6 7)) => 4

A deep function is a function which operates on the given list, and all the contained lists.


  • Count atoms -- deep
(defun count-atoms-deep (l)
    (cond
        ((null l) 0)
        ((atom (car l))
            (1+ (count-atoms-deep (cdr l))))
        (t
            (+
                (count-atoms-deep (car l))
                (count-atoms-deep (cdr l))))
    ))

(count-atoms-deep '(1 2 (3 4 5) 6 7)) => 7


Recursive functions

[edit]

Tail and shallow recursive functions

[edit]

Rewrite the standard functions:

  • my-member
  • my-length
  • my-append
  • my-reverse-shallow
(my-reverse-shallow '(1 2 3 ((4)) (5 6 7) 8 9)) => (9 8 (5 6 7) ((4)) 3 2 1)
  • my-substitute -- the shallow version
  • my-remove-shallow
(my-remove-shallow 1 '(1 2 3 (1 2 3 4 (1)))) => (2 3 (1 2 3 4 (1)))

Write the following functions:

  • count-atoms
  • sum
  • unique
(unique '(1 2 3 1 2 3 4 5 5 5 6)) => (1 2 3 4 5 6)
  • my-min-shallow
(my-min-shallow '(1 2 3 4 5)) => 1

(defun my-min-shallow-a (l m)
    (cond
        ((null l) m)
        ((< (car l) m)
            (my-min-shallow-a (cdr l) (car l)))
        (t
            (my-min-shallow-a (cdr l) m))
    ))
(defun my-min-shallow (l)
    (my-min-shallow-a (cdr l) (car l)))

(my-min-shallow '(1 2 3 4 5)) => 1
(my-min-shallow '(2 1 3 4)) => 1
(my-min-shallow '(4 5 3 1)) => 1
  • my-max-shallow
  • my-list-equal-shallow
(my-list-equal '(1 2 3) '(1 2 3)) => t
  • prime-p
(prime-p 2) => t
(prime-p 4) => nil
  • div-sum -- the sum of the divisors of the given number
(div-sum 6) => 2 + 3 => 5

(defun div-sum-a (n d s)
    (cond
        ((= d n) s)
        ((zerop (mod n d))
            (div-sum-a n (1+ d) (+ s d)))
        (t
            (div-sum-a n (1+ d) s))
    ))
(defun div-sum (n)
    (div-sum-a n 2 0))

(div-sum 6) => 5
(div-sum 10) => 7
(div-sum 1000) => 1339
  • digit-sum -- the sum of the digits of the given number
(digit-sum 12345) => 15

Deep functions

[edit]
  • my-reverse-deep
(my-reverse-deep '(1 2 3 ((4)) (5 6 7) 8 9)) => (9 8 (7 6 5) ((4)) 3 2 1)
  • my-substitute-deep
  • my-remove-deep
(my-remove-deep 1 '(1 2 3 (1 2 3 4 (1)))) => (2 3 (2 3 4 ()))
  • my-min-deep
(my-min-deep '(10 2 (1) 5 6)) => 1

(defun my-min-deep-a (l m)
    (cond
        ((null l) m)
        ((listp (car l))
            (min (my-min-deep-a (car l) m) (my-min-deep-a (cdr l) m)))
        (t
            (my-min-deep-a (cdr l) (min (car l) m)))
    ))
(defun my-min-deep (l)
    (my-min-deep-a l most-positive-fixnum))

(my-min-deep '(2 3 4 (1 2 3 (0)))) => 0
(my-min-deep nil) => most-positive-fixnum
  • my-max-deep
  • my-list-equal-deep
(my-list-equal-deep '(1 (2) 3) '(1 (2) 3)) => t
  • flatten
(flatten '(1 2 (3 4 5 (6) (()) 7) 8)) => (1 2 3 4 5 6 7 8)

(defun flatten (l)
    (cond
        ((null l) nil)
        ((listp (car l))
            (append (flatten (car l)) (flatten (cdr l))))
        (t
            (cons (car l) (flatten (cdr l))))
    ))

(flatten '((1 2 3) 4 (5 (6 (7 8 9))))) => (1 2 3 4 5 6 7 8 9)


More exercises

[edit]


Assignment 3

[edit]

For the next week you don't have a home assignment.

But instead you will sustain a short test at the beginning of the next week lab. The problems will be about recursive functions:

  • tail recursive functions
  • deep functions

For examples please consult the previous list.

Ciprian Dorin Craciun

2007-03-15

ccraciun@info.uvt.ro