<< lekcja 13 | lekcja 15 >>
14. Rekursja a iteracja
W LISP istnieje kilka instrukcji (makr i form specjalnych) pozwalających wykonywać wielokrotnie ten
sam fragment kodu. W tradycyjnym programowaniu służą do tego instrukcje iteracyjne oraz rekurencyjne
wywołania pewnych funkcji. Podobnie jest w LISP.
14.1 Iteracja
Isnieje kilka instrukcji pozwalająych dokonywać iteracji, czy to na kolejnych liczbach naturalnych,
czy to na kolejnych elementach listy, a także w sposób zdefiniowany przez programistę. Oto one.
14.1.1 loop
Najprostaszą konstrukcją iteracyną w LISP jest (loop body), ktora kolejno, w nieskonczonosc wykonuje formy zawarte w body.
Ponieważ instrukacja ta jest niejawnie otoczna instrukcją (block nil) mozna ja przerwać tylko przy pomocy instrukcji
(return) lub (return var). W pierwszym przypadku zostanie zwrocona wartosc nil, w drugim zaś var.
14.1
> (setq a 4) => 4
> (loop
(setq a (+ a 1))
(when (> a 7) (return a))
) => 8
> (loop
(setq a (- a 1))
(when (< a 3) (return))
) => NIL
|
14.1.2 dotimes
Konstrukcja dotimes pozwala w łatwy sposób wykonać kilkakrotnie ten sam fragment kodu ze zmiennymi
będącymi kolejnymi liczbami naturalnymi. Ma ona postać (dotimes (var n) body). Pętla ta wykonuje się
n razy, przy czym var przyjmuje w kolejnych iteracjach wartości o 0 do n-1. Na końcu zwaracne jest
nil.
14.2
> (dotimes (i 4)
(format t "~&I is ~S." i)) =>
I is 0.
I is 1.
I is 2.
I is 3.
NIL
|
14.1.3 dolist
Instrukajca ta pozwala w łatwy sposób dokonywać pewnych operacji na wszystkich elementach listy. Ma ona postać
(dolist (var list) body). Każdy element list jest kolejno przypisywany do zmiennej var, po czym wykownywane jest body,
aż do osiągnięcia końca listy.
14.3
> (dolist (x ’(a b c)) (print x)) =>
A
B
C
NIL
|
W najprostszej postaci dolist zwraca nil
14.1.4 do
Najbardziej skomplikowaną instrukcją związanąz iteracją jest do. Ma ona następującą postać
(do ((var1 start1 step1)
(var2 start2 step2) ...)
(condition resultform)
body)
Na początku zmienne var1, var2, ... za wiązane z wartościami start1, start2, ... Jeśli wartość nie jest podana wartość
początkowa, to zmienne otrzymują wartość nil. Badany jest condition (warunek). Jeśli jest on spełniony, to iteracje są
przerywane i do zwraca resultform. Jeśli warunek nie jest spełniony, to wykonywane jest body, a w kolejnych iteracjach
zmiennym var1, var2, ... przypisywane są wartości step1, step2,... Jeśli dla danej zmiennej nie
występuje step, to zmienna ta pozostaje bez zmian w kolejnych krokach iteracji (chyba, że modyfikowana
jest w body).
14.4>
(do ((x 1 (+ x 1))
(y 1 (* y 2)))
((> x 5) y)
(print y)
(print ’working)
) =>
1
WORKING
2
WORKING
4
WORKING
8
WORKING
16
WORKING
32
|
Zmienne są wiązane analogicznie jak w let. Istniej też forma do*, w któej wiązanie następuje identycznie
jak w let*.
14.1.5 mapcar
Niektóre pętle typu dolist dają się znacznie zgrabniej wyrazić w postaci instrukcji mapcar, która
wywołuje pewną funkcję na każdym elemencie listy. Ma ona postać (mapcar f list).
14.5
(defun square (n) (* n n)) => square
(mapcar #'squara '(1 2 3 4 5)) => (1 3 9 16 25)
|
Widzimy więc, że jest ona podobna do instrukcji apply, różni się jednak traktowaniem listy argumentów.
Applay przekazuje wszystkie argumenty należące do listy argumentów "za jednym zamachem", podczas
gdy mapcar przekazuje argumenty każdy z osobna.
Jeżeli funkcja f przyjmuje więcej argumentów niż 1, to wszystki argumenty kolejnych wywołań zgrupowana
są w osobnych listach.
14.6
(mapcar #'+ '(1 2 3) '(1 2 3)) => (2 4 6)
|
14.1.6 mapcan
Uzupełnieniem instrukcji mapcar jest instrukacja mapcan, która usuwa wartości nil z listy wynikowej.
Wynik jest identyczny temu, który uzysklibyśmy stosują do listy wynikowej instrukcję nconc.
14.7
(defun inc (n)
(cond ((numberp n) (+ n 1))
(t nil)
)
) => inc
(inc 1) => 2
(inc 'a) => nil
(mapcan #'inc '(1 a 2 b 3 c)) => (2 3 4)
|
14.2 Rekursja
Podobnie jak w innych językach programowania w LISP rekursję otrzymujemy poprzez powtórne wywołani
funkcji w jej własnym ciele. Oczywiścia aby rekursja miała sens potrzeba aby były spełnione następujące
3 warunki:
- rekursja musi mieć warunek stopu,
- powinien być wyróżniony podstawowy krok rekursji,
- kolejne wywołanie rekursyjne powinno odbywać się dla struktury o jeden mniejszej niż otrzymana
na wejści.
Oto przykład rekursji w LISP:
14.8
(defun silnia (n)
(cond ((< n 2) n)
(t (* n (silnia (- n 1))))
)
) => silnia
(silnia 5) => 120
|
Ponieważ w LISP nie ma ograniczeń na wartości liczb całkowitych (jedynym ograniczeniem jest wielkość
stosu, czyli mówiąc ogólnie wielkość pamięci operacyjnej) powyższe wywołanie daje poprawne wyniki
dla całkiem dużych wartości n, w porównaniu z takimi językami jak np. C.
<< lekcja 13 | lekcja 15 >> |