[tell_me_more]

#programowanie #learnclojurewithmikroblog #clojure

Odcinek 4 - rekurencja ogonowa, loop recur, do

W clojure nie ma pętli for, bo nie używa się zmiennych(nie do końca prawda, ale na razie tego się trzymajmy). Pętle implementuje się rekurencją, lub używa funkcji wyższego rzędu, które mają pętlę w środku. Jednak rekurencja ma przecież poważną wadę - zużywa stos. Przykład:

(

defn 
```**```
while-true-hell-world []
``````
      (println "hello world")
``````
      (while-true-hell-world))
``````
; zrobmy petle nieskonczona
``````
(while-true-hell-world) ; zwraca java.lang.StackOverflowError
```Czy nie da się tego uniknąć? Przecież pętla z tysiącami obrotów to nic nadzwyczajnego, a stos tego nie wytrzyma. Problem został zauważony i rozwiązany już w początkach istnienia języka lisp - rozwiązaniem jest [http://pl.wikipedia.org/wiki/Rekurencja_ogonowa](http://pl.wikipedia.org/wiki/Rekurencja_ogonowa) .Otóż rekurencja zużywa stos tylko dlatego, że kiedy wracamy z funkcji podrżednej do funkcji nadrzędnej - musimy wiedzieć do którego miejsca w funkcji nadrzędnej wrócić, i jakie były wartości zmiennych lokalnych tej funkcji. Jeśli by się zdarzyło, że w funkcji nadrzędnej nie trzeba nic już robić po powrocie z funkcji podrzędnej - w ogóle nie musimy wstawiać funkcji nadrzędnej na stos! Po prostu traktujemy wywołanie funkcji podrzędnej jak niesławne GOTO - przeskakujemy do podrzędnej i tyle. Nie trzeba wracać.Założenie jest tu niesłychanie ważne - kompilator musi wiedzieć, że po powrocie z funkcji podrzędnej nic nie będzie musiał robić w funkcji nadrzędnej. Kilka przykładów funkcji rekurencyjnych umożliwiających tą optymalizację i nie, żeby łatwo można było poznać:```
(
```**```
defn 
```**```
odlicz [n]
``````
      (
```**```
println 
```**```
n)
``````
      (
```**```
if 
```**```
(
```**```
> 
```**```
n 0)
``````
          (odlicz (
```**```
- 
```**```
n 1)))) 
``````
; tutaj po powrocie z podrzędnego wywołania nic nie robimy - to jest rekurencja ogonowa
``````
(
```**```
defn 
```**```
odlicz [n]
``````
      (
```**```
if 
```**```
(
```**```
> 
```**```
n 0)
``````
          (odlicz (
```**```
- 
```**```
n 1)))
``````
      (
```**```
println 
```**```
n))
``````
; tutaj po powrocie z podrzędnego wywołania robimy coś jeszcze - to NIE jest rekurencja ogonowa
``````
(
```**```
defn 
```**```
silnia [n]      
``````
      (
```**```
if 
```**```
(
```**```
< 
```**```
n 2)
``````
          1
``````
          (
```**```
* 
```**```
(silnia (
```**```
- 
```**```
n 1)) 
``````
             n))) 
``````
; tutaj po powrocie z podrzędnego wywołania mnożymy przez n, więc to NIE JEST rekurencja ogonowa
``````
(
```**```
defn 
```**```
silnia [n acc]
``````
      (
```**```
if 
```**```
(
```**```
< 
```**```
n 2)
``````
          1
``````
          (silnia (
```**```
- 
```**```
n 1)
``````
                  (
```**```
* 
```**```
n acc))))
``````
; tutaj mnożenie wykonujemy przed wywołaniem podrzędnej funkcji, a po tym wywołaniu już nic nie robimy tylko zwracamy wynik. Oznacza to, że TO JEST REKURENCJA OGONOWA
``````
W silni potrzebujemy coś zrobić z wynikiem wywołania podrzędnego, a nie możemy tego zrobić po powrocie z funkcji (bo by to nie było wywołanie ogonowe), więc stosujemy trick z akumulatorem (dodatkowa zmienna przekazywana w której trzymamy tymczasowy wynik)
```**```
. 
```**```
Zwyczajowo taką zmienną nazywa się acc.
``````
Ok, skoro mamy rekurencję ogonową, to clojure jako język funkcyjny sobie poradzi bez zapychania stosu, tak? NIE. Clojure działa głównie na JVM, i autorzy języka nie mogli sobie poradzić z napisaniem wykrywania pozycji ogonowej w deterministryczny sposób (nie znam szczegółów)
```**```
. 
```**```
Zamiast tego zrobili makro 
```**```
loop 
```**```
**`- `**`recur, które służy `**`do `**`zrobienia pętli z rekurencją ogonową`**`. `**`Przykład silni z `**`loop `**
```**```
- 
```**```
recur:
``````
(
```**```
defn 
```**```
silnia [x]
``````
    (
```**```
loop 
```**```
[n   x   ; wartosci dla
``````
           acc 1]  ; pierwszego wywolania
``````
        (
```**```
if 
```**```
(
```**```
= 
```**```
n 1)
``````
            acc
``````
            (recur (
```**```
dec 
```**```
n)       ; rekurencja
``````
                   (
```**```
* 
```**```
acc n))))) ; ogonowa
```loop jest podobne do funkcji - wprowadza nowy zasięg (scope), i w ramach niego deklaruje parametry z przypisanymi wartościami. Następnie recur skacze rekursywnie do odpowiadającego mu loop z nowymi wartościami dla tych parametrów. To nie jest pętla, choć wygląda jak pętla - to działa, jak rekursywne wywołanie funkcji, ale nie zużywa stosu.Co ciekawe - clojure upewni się, czy na pewno recur jest w pozycji ogonowej. Przykład (durny):```
 (
```**```
defn 
```**```
silnia [x]
``````
    (
```**```
loop 
```**```
[n   x   ; wartosci dla
``````
           acc 1]  ; pierwszego wywolania
``````
        (
```**```
if 
```**```
(
```**```
= 
```**```
n 1)
``````
            acc
``````
            (
```**```
* 
```**```
1 (recur (
```**```
dec 
```**```
n)
``````
                   (
```**```
* 
```**```
acc n))))))
````; zwróci wyjątek podczas definiowania funkcji: java.lang.UnsupportedOperationException: Can only recur from tail positionJeszcze jedna rzecz, bo może się przydać - czasem potrzeba pogrupować kilka wyrażeń, zrobić coś, jak```
    BEGIN
``````
        coś();
``````
        cośInnego();
``````
    END
``````
w pascalu, lub 
``````
    {
``````
        coś();
``````
        cośInnego();
``````
    }
````w językach o skłądni podobnej do C.W clojure robi się to tak:```
    (
```**```
do 
```**```
(coś)
``````
           (cośInnego))

Takie wyrażenie wyliczy wyrażenia coś, potem cośInnego , po czym zwróci wynik ostatniego. Działa dla dowolnej liczby wyrażeń. Szczególnie przydaje się w połączeniu z (if warunek na-true na-false)

Zadanie 4. Napisać funkcję (do-times [f n] ...) ; która wykona n razy funkcję bezargumentową f i zwróci jej ostatni wynik. Wykorzystać recur.

[tell_me_more]

Rozwiązanie zadania 3. (zrobił @rubberbandman, ciężko to napisać inaczej :) )

http://pastebin.com/xi5794x4

Jak zwykle proszę o uwagi.