Racket CheatSheet

Laborator 2

Recursivitate pe stivă Recursivitate pe coadă Sintaxa Racket

(nume functie arg1 arg2 ...)
1 ; suma elementelor unei liste 1 ; suma elementelor unei liste
2 (define (sum-list L) 2 (define (sum-list L) 1 (max 2 3) 3
3 3 (sum-list-tail 0 L)) ; <-- funct, ie ajutătoare 2 (+ 2 3) 5
4 4 ; ˆ valoarea init, ială pentru sumă
5 ; aici nu avem nevoie de funct, ie auxiliară 5
6 6 ; ı̂n sum construim rezultatul AS, A DA / AS, A NU
7 7 (define (sum-list-tail sum L)
8 (if (null? L) 8 (if (null? L)
1 DA: (cons x L) NU: (append (list x) L)
9 0 ; la sfârs, it creăm valoarea init, ială 9 sum ; la sfârs, it avem rezultatul gata
2 NU: (append (cons x '()) L)
10 (+ (car L) (sum-list (cdr L))) 10 (sum-list-tail
3 DA: (if c vt vf) NU: (if (equal? c #t) vt vf)
11 ; ˆ construim rezultatul pe revenire 11 (+ sum (car L))
4 DA: (null? L) NU: (= (length L) 0)
12 ; (după ı̂ntoarcerea din recursivitate) 12 ; ˆ construim rezultatul pe avans
5 DA: (zero? x) NU: (equal? x 0)
13 )) 13 ; (pe măsură ce intrăm ı̂n recursivitate)
6 DA: test NU: (if test #t #f)
14 ; fiecare apel recursiv ı̂ntoarce rezultatul 14 (cdr L))))
7 DA: (or ceva1 ceva2) NU: (if ceva1 #t ceva2)
corespunzător argumentelor 15 ; funct, ia ı̂ntoarce direct rezultatul apelului
8 DA: (and ceva1 ceva2) NU: (if ceva1 ceva2 #f)
15 recursiv -- toate apelurile recursive ı̂ntorc
16 acelas, i rezultat, pe cel final
17 16
18 17 Imagini ı̂n Racket
19 ; concatenarea a două liste 18 ; concatenarea a două liste
20 (define (app L1 L2) 19 (define (app A B)
image-height, overlay, flip-vertical
21 20 (app-iter B (reverse A)))
22 21 ; nevoie de funct, ie ajutătoare
23 22 ; rezultatul este construit ı̂n ordine inversă
24 23
25 24 (define (app-iter B Result) 1 (overlay ) ; =>
26 (if (null? L1) 25 (if (null? B) ; la sfârs, it rezultatul e complet
27 L2 ; când L1 este vidă, ı̂ntoarcem L2 26 (reverse Result) ; inversăm rezultatul
28 (cons (car L1) (app (cdr L1) L2)) 27 (app-iter (cdr B) (cons (car B) Result))))
29 ; ˆ construim rezultatul pe revenire)) 28 ; construim rezultatul pe avans
2 (flip-vertical ) ; =>
3 (image-height (circle 20 "solid" "red")) ; => 40
• fiecare apel recursiv se pune pe stivă • apelurile recursive nu consumă spat, iu pe stivă –
• complexitate spat, ială O(n) execut, ia este optimizată s, tiind că rezultatul ape-
lului recursiv este ı̂ntors direct, fără operat, ii supli-
• scriere mai simplă mentare. 4 (image-height ) ; => 60
• complexitatea spat, ială este dată doar de spat, iul
necesar pentru acumulator – de exemplu la
Folosit, i cu ı̂ncredere!
sum-list-tail complexitatea spat, ială este
O(1). [Link]

• scriere mai complexă, necesită de multe ori funct, ie

auxiliară pentru a avea un parametru suplimentar
pentru construct, ia rezultatului (rol de acumula-
tor), mai ales dacă tipul natural de recursivitate
al funct, iei este pe stivă.
– Atent, ie: uneori, rolul acumulatorului poate
fi preluat de unul dintre parametri, caz ı̂n care
nu este nevoie nici de funct, ia suplimentară.
• rezultatul este construit ı̂n ordine inversă