W dniu piątek, 5 stycznia 2018 11:51:07 UTC+1 użytkownik Maciej Sobczak napisał:
> > I mówiąc to, mam na myśli, że przy pomocy rekurencji można zdefiniować
> > iterację, natomiast przy pomocy iteracji nie można zdefiniować rekurencji.
>
> Tak. Rekurencja jest bardziej ogólnym mechanizmem w tym sensie, że uogólnia pojęcie
powtórzenia. I to wcale nie sprawia, że jest łatwiejsza do zrozumienia.

Nie sprawia. Ale nie sprawia też, że jest trudniejsza do zrozumienia.
Jak wspominałem w toku naszej dyskusji, są zagadnienia, których nie
potrafimy zrozumieć inaczej, niż rekurencyjnie.

> > I w tym sensie iteracja jest prostsza od rekurencji, że ma mniejszą
> > siłę wyrazu (można przy jej pomocy zrobić mniej)
>
> Zgadza się. Ale iteracja ma jedną gigantyczną zaletę: można przy pomocy iteracji
zrobić iterację. I tam, gdzie potrzebna/wystarczajaca jest iteracja, wybór iteracji
jako narzędzia jest bardziej właściwy - prostszy mechanizm, który potrafi mniej, jest
wtedy łatwiejszy do zrozumienia. Bywa, że jest wtedy też bardziej wydajny. Dlatego
używanie rekurencji do robienia iteracji jest przerostem formy, być często nawet
zwykłym snobizmem.

Co do istoty, iteracja nie jest bardziej wydajna, niż rekurencja,
bo iteracja jest tylko specjalizacją rekurencji.

Dobrze jest to wyjasnione w "Strukturze i Interpretacji Programów
Komputerowych", gdzie odróżnia się rekurencyjne i iteracyjne procesy
obliczeniowe od rekurenyjnych i iteracyjnych definicji (środka wyrazu).

> Analogia warsztatowa: zwykły młotek może zrobić mniej, niż kombajn ogólnego
przeznaczenia func'o'matic. I dlatego do wielu zastosowań młotek będzie lepszym
wyborem. A warsztat, który w ogóle nie ma młotka, jest po prostu nieużyteczny, nawet
jeśli ma kombajn func'o'matic.

Analogia jest o tyle nietrafna, że w przypadku dyskusji "rekurencja
vs. iteracja" mamy do czynienia nie tylko z aspektem możliwości, ale również
złożoności. Młotek może mniej niż kombain func'o'matic, ale młotek jest też
prostszy (mniej złożony) od takiego kombajnu.
Rekurencja natomiast zarówno może więcej (jest mniej wyspecjalizowana),
jak również jest prostsza (w sensie złożoności) od iteracji.

To jest istotne o tyle, że gdyby ktoś trzymał się dwóch zasad:
"stosuj najprostsze narzędzia dla osiągnięcia danego celu"
oraz
"do danego celu stosuj narzędzia wymagające jak najmniejszej mocy",
to te dwie raczej (wg. mnie) rozsądnie brzmiące maksymy mogą w wielu
sytuacjach stać ze sobą w sprzeczności.

Istotna wydaje się też kwestia przypadkowej złożoności.

W przypadku podanego przez Ciebie przykładu, zrozumienie zapisu x[[1 ;; ;; 2]]
wymaga odwołania do dokumentacji - składnia Mathematiki jest źródłem
przypadkowej złożoności, bo jej znaczenia nie da się wywnioskować
z "pierwszych zasad". W rozwiązaniu Kaya jedyna przypadkowa złożoność
jest w nazwach. Ale w tej kwestii z pomocą przychodzi nam dorobek
Burstalla, który rozszerzył ISWIM o pattern-matching, i teraz
np. w takim Haskellu zamiast

where odds(x) = if null(x) ? null(tl(x)) then x
else hd(x) & odds(ttl(x))
evens(x) = if null(x) ? null(tl(x)) then nil
else odds(tl(x))

napisalibyśmy raczej coś w stylu

where odds(o:e:xs) = o:odds(xs)
odds(xs) = xs
evens(o:xs) = odds(xs)
evens(xs) = []

W tym przypadku złożoność przypadkowa została praktycznie wyrugowana
do minimum: zasadniczo wszystko można wywnioskować z "pierwszych zasad"

> Używajmy właściwych narzędzi do ich najbardziej naturalnych zastosowań, gdzie słowo
"naturalne" zostawię już bez rozwinięcia, bo rozgrzebywanie takich definicji nie jest
moją intencją na tej grupie.

Myślę, że nikt tutaj nie będzie się spierał o to, żeby używać narzędzi
do ich najbardziej naturalnych zastosowań, i jedynym, o co można się
spierać, jest to jak należy rozumieć słowo "naturalne".