Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 5
Appearance
References
[edit]From the book Sketchy Lisp: the Tail-Recursive Programs section.
From the book Successful Lisp: Tail recursion.
Or from wikipedia:Tail recursion Tail recursion.
Examples
[edit]- Arithmetic
n!
(factorial):
(defun n!* (n acc) (if (zerop n) acc (n!* (1- n) (* acc n)))) (defun n! (n) (n!* n 1)) (print (n! 0)) (print (n! 1)) (print (n! 2)) (print (n! 10))
fibonacci
:
(defun fibonacci* (n a1 a2) (if (<= n 1) a1 (fibonacci* (1- n) a2 (+ a1 a2)))) (defun fibonacci (n) (fibonacci* n 1 1)) (print (fibonacci 1)) (print (fibonacci 2)) (print (fibonacci 3)) (print (fibonacci 10))
- Arithmetic over lists
list-sum
:
(defun list-sum* (lst sum) (cond ((null lst) sum) ((numberp (first lst)) (list-sum* (rest lst) (+ sum (first lst)))) (t (list-sum* (rest lst) sum)))) (defun list-sum (lst) (list-sum* lst 0)) (print (list-sum nil)) (print (list-sum '(1))) (print (list-sum '(1 a 2)))
list-min
:
(defun list-min* (lst m) (cond ((null lst) m) ((not (numberp (first lst))) (list-min* (rest lst) m)) ((< (first lst) m) (list-min* (rest lst) (first lst))) (t (list-min* (rest lst) m)))) (defun list-min (lst) (list-min* (rest lst) (first lst))) (print (list-min nil)) (print (list-min '(1))) (print (list-min '(1 a))) (print (list-min '(2 a 1 b 3)))
- Recursion over lists
list-random
: creates a list of a given length, with random (integer) numbers from 0 up to a given limit.
(defun list-random* (length limit acc) (if (zerop length) acc (list-random* (1- length) limit (cons (random limit) acc)))) (defun list-random (length limit) (list-random* length limit nil)) (print (list-random 0 1000)) (print (list-random 10 1000))
list-reverse
:
(defun list-reverse* (lst rev) (if (null lst) rev (list-reverse* (rest lst) (cons (first lst) rev)))) (defun list-reverse (lst) (list-reverse* lst nil)) (print (list-reverse nil)) (print (list-reverse '(1))) (print (list-reverse '(1 a 2)))
list-clone
:
(defun list-clone (lst) (list-reverse* (list-reverse* lst nil) nil)) (print (list-clone nil)) (print (list-clone '(1))) (print (list-clone '(1 a 2)))
- Recursion over ordered
ordered-insert
:
(defun ordered-insert* (lst x acc) (cond ((and (null lst) (null x)) acc) ((null lst) (ordered-insert* nil nil (cons x acc))) ((null x) (ordered-insert* (rest lst) nil (cons (first lst) acc))) ((< x (first lst)) (ordered-insert* lst nil (cons x acc))) (t (ordered-insert* (rest lst) x (cons (first lst) acc))))) (defun ordered-insert (lst x) (reverse (ordered-insert* lst x nil))) (print (ordered-insert '() 5)) (print (ordered-insert '(1) 5)) (print (ordered-insert '(10) 5)) (print (ordered-insert '(1 5 10) 5))
Exercises
[edit]Redo all the exercises from the previous laboratories, but this time in a tail recursive manner: