Neprogramátor/Rekurze, iterace, nebo cyklus?

Rekurze, iterace i cyklus souvisí s opakováním.

Rekurze je, když kouzelná hůlka vykonává kouzelnou větu, ve které potřebuje vykonat jinou kouzelnou větu začínající stejným kouzelným slovesem.

Iterace je, když kouzelná hůlka opakuje kouzelné věty, ve kterých se mění informace ukryté v některých kouzelných podstatných jménech.

Cyklus je, když kouzelná hůlka opakuje kouzelné věty, dokud jedna z těch kouzelných vět (ne)platí.

Na co se opakování hodí? Třeba na určení cen položek nákupního seznamu

(define nákupní-seznam '("ředkvičky" "rum" "rýže" "tofu" "minerálka"))

když cena položky je

(define (cena položky)
  (string-length položky))

Při použití rekurze čaroděj naučí kouzelnou hůlku nové kouzelné sloveso ceny-položek kouzelnou větou

(define (ceny-položek seznam)
  (if (null? seznam)
      '()
      (cons (cena (first seznam)) (ceny-položek (rest seznam)))))

kterou pak může použít v kouzelné větě

(ceny-položek nákupní-seznam)

'(9 3 4 4 9)


Pro použití iterace má čaroděj v záloze kouzelnou větu začínající kouzelným slovesem do. Kouzelné věty začínající kouzelným slovesem do mají jinou gramatiku než kouzelné věty používající rekurzi.

(do ((pracovní-seznam nákupní-seznam (rest pracovní-seznam))
     (ceny-položek '() (append ceny-položek (list (cena (first pracovní-seznam))))))
    ((= (length ceny-položek) (length nákupní-seznam)) ceny-položek))

'(9 3 4 4 9)

Druhé a třetí slovo kouzelné věty začínající kouzelným slovesem do je seznam, který nezačíná apostrofem a závorkou '(, ale jen závorkou (. Druhé slovo kouzelné věty obsahuje nová kouzelná podstatná jména, každé ve vlastním seznamu, který zase začíná jen závorkou (. Třetí slovo kouzelné věty obsahuje predikát a kouzelné slovo či větu, kterou kouzelná hůlka vyhodnotí a vrátí jako výsledek kouzelné věty začínající kouzelným slovesem do, pokud predikát platí.

(pracovní-seznam nákupní-seznam (rest pracovní-seznam)) učí kouzelnou hůlku nové kouzelné podstatné jméno pracovní-seznam, které má na začátku, před spuštěním do, stejnou hodnotu jako nákupní-seznam a při každém kroku iterace se jeho hodnota změní na (rest pracovní-seznam).

(ceny-položek '() (append ceny-položek (list (cena (first pracovní-seznam))))) učí kouzelnou hůlku nové kouzelné podstatné jméno ceny-položek, které je na začátku prázdný seznam a při každé další iteraci se do seznamu ceny-položek přidá cena první položky seznamu pracovní-seznam, tedy (cena (first pracovní-seznam)).

Kouzelné sloveso append spojuje dva seznamy. Výsledek vyhodnocení kouzelné věty začínající kouzelným slovesem cena je ale číslo. Proto je potřeba kouzelnou větu začínající kouzelným slovesem cena vložit do kouzelné věty začínající kouzelným slovesem list.

((= (length ceny-položek) (length nákupní-seznam)) ceny-položek) říká kouzelné hůlce, že pokud je délka seznamu ceny-položek stejná jako délka seznamu nákupní-seznam, má kouzelná hůlka ukončit opakování a vrátit hodnotu kouzelného podstatného jména ceny-položek.

Iterace zapsaná v kouzelné větě výše ale neopakuje žádné věty! Je to proto, že problém, který iterace řeší, lze zapsat jen pomocí druhého a třetího slova. Čaroděj může ale jeden problém řešit více způsoby.

(do ((i 0 (+ 1 i))
     (ceny-položek '()))
    ((= i (length nákupní-seznam)) ceny-položek)
  (set! ceny-položek
        (append ceny-položek
                (list (cena (list-ref nákupní-seznam i))))))

'(9 3 4 4 9)

(i 0 (+ 1 i)) učí kouzelnou hůlku nové kouzelné podstatné jméno i, které má na začátku hodnotu 0 a při každém kroku iterace se jeho hodnota o 1 zvýší.

(ceny-položek '()) učí kouzelnou hůlku nové kouzelné podstatné jméno ceny-položek, které má na začátku hodnotu '() a při kroku iterace se jeho hodnota nemění. Protože ale podle ((= i (length nákupní-seznam)) ceny-položek) se kouzelné podstatné jméno ceny-položek má použít jako výsledek vyhodnocení kouzelné věty začínající kouzelným slovesem do ve chvíli, kdy je i stejné jako počet položek nákupního seznamu nákupní-seznam, bude potřeba hodnotu kouzelného podstatného jména ceny-položek s každou iterací změnit. To je účel kouzelné věty

(set! ceny-položek
      (append ceny-položek
              (list (cena (list-ref nákupní-seznam i)))))

Kouzelná věta začínající kouzelným slovesem set! změní hodnotu kouzelného podstatného jména. To je vedlejší jev (side effect). Vedlejší jevy jsou nepostradatelné, ale všechno jen komplikují. Je lepší se jim vyhnout. Nejdůležitější principy programování lze vysvětlit i bez vedlejších jevů.

Vyhodnocením kouzelné věty (list-ref nákupní-seznam i) je kouzelné podstatné jméno ukryté v seznamu nákupní-seznam na pozici číslo i, kde první položka na pozici 0.

Ve spoustě programovacích jazyků se kouzelné věty iterace, které používají i v rozsahu od 0 do konce délky seznamu, píší zejména pomocí kouzelného slovesa for. V programovacím jazyce Racket je kouzelné sloveso for podobné spíše přístupu "for each", kdy se iteruje nikoli přes číslo pozice položky seznamu i, ale přímo přes položku seznamu položka:

(for ((položka nákupní-seznam)
      (ceny-položek '()))
  (set! ceny-položek
        (append ceny-položek
                (list (cena položka)))))

'(9 3 4 4 9)


Pro cyklus lze opět použít kouzelnou větu začínající kouzelným slovesem do. V ostatních programovacích jazycích by se nejspíš použilo kouzelné sloveso while, to ale v Racket není.

(define ceny-položek '())
(define i 0)
(do ()
    ((= (length ceny-položek) (length nákupní-seznam)))
  (set! ceny-položek
        (append ceny-položek
                (list (cena (list-ref nákupní-seznam i)))))
  (set! i (+ 1 i)))
ceny-položek

'(9 3 4 4 9)

Kouzelná věta začínající kouzelným slovesem do v tomto případě pouze zkontroluje, jestli jsou délky seznamů ceny-položek a nákupní-seznam stejné a pokud ano, opakování skončí. (Takže opakování pokračuje, pokud se délky seznamů liší.) Opakovány jsou kouzelné věty s kouzelnými slovesy set!, které pomocí vedlejších jevů mění hodnoty kouzelných podstatných jmen ceny-položek a i. Výsledek je ukrytý v kouzelném podstatném jméně ceny-položek.