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

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

Linear recursion

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

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

Fibonacci function:

(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

Ackermann function:

(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

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

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

Tail and shallow recursive functions

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

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

Assignment 3

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