# Functional programming -- 2008-2009 -- info.uvt.ro/Laboratory 5

 Functional programming (Spring 2010): front; laboratory: agenda, references, projects, tools; notes (normal paced): 1, 2, 3, 4, 5, 6, 7, 8 (Spring 2009); notes (fast paced): 1, 2, 3, 4 (Spring 2010) (discontinued); applications: robots; mailing list: send mail, view archive, subscribe; author: Ciprian Dorin Craciun, ccraciun@info.uvt.ro;

## References

From the book Sketchy Lisp: the Tail-Recursive Programs section.

From the book Successful Lisp: Tail recursion.

## Examples

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

Redo all the exercises from the previous laboratories, but this time in a tail recursive manner: