Rekurencja jest o jedno piętro abstrakcji wyżej niż interacja. Źle
użyta może mieć złe skutki. Ale dobrze użyta jest ok. Np.
trywializuje obliczanie wielomianów Czebyszewa.

Lęk przed rekurencją to lęk przed abstrakcją.

Z drugiej strony w wielu programach, zwłaszcza aplikacjach Windows,
pojawia się w niekontrolowany sposób rekurencja pośrednia. Czyli a
woła b, b woła c, ..., x woła a. To może być jakiś tercet
update-invalidate-paint. Takiej rekurencji mówimy stanowcze nie.

do góry

On Wed, 3 Jan 2018 01:58:10 -0800 (PST), Maciej Sobczak wrote:

>> Nazwa "sortowanie bąbelkowe" wzięła się od pewnej metafory,
>
> Z obserwacji natury. :-)
>
>> Nie do końca rozumiem, co masz na myśli mówiąc o "procesach naturalnych".
>
> Takich, które występują w naturze. Wliczamy w to procesy fizyczne, chemiczne, itp.
>
>> Jeżeli mamy kurę, która składa jajko, z którego wykluwa się kura, która
>> składa jajko, z którego wykluwa się ..., to czy to nie jest proces
>> reKUREncyjny par excellence?
>
> Ciekawy przykład, ale Słońce też wschodzi i zachodzi i znowu wschodzi. Deszcz pada,
potem woda paruje a potem z tej pary robią się chmury i znowu pada. Itd. Jeśli coś
się powtarza, to mówimy, że jest to cykl. Pojęcie rekurencji nie jest do tego
potrzebne ani nie ułatwia rozumienia tych zjawisk. Z jakiegoś powodu wszystkie takie
zjawisko omawia się w przedszkolach, na szczęście dla przedszkolaków bez rekurencji.

A może weźmy pod uwagę fraktale? W naturze jest ich multum. Czy taki
przykład jest ok?

--
pozdrawiam
Roman Tyczka

do góry

> A może weźmy pod uwagę fraktale? W naturze jest ich multum. Czy taki
> przykład jest ok?

W naturze nie ma fraktali. Ani jednego.

Istnieją struktury, które były inspiracją albo wywołują jakieś skojarzenia
fraktalowe, np. liść paproci. Ale problem w tym, że te struktury powstają
iteracyjnie, dzięki zupełnie lokalnym procesom komórkowym, które o naszych
rekurencyjnych skojarzeniach nic nie wiedzą.

Tu jest fajny przykład:

https://en.wikipedia.org/wiki/Rule_90

Zjedź trochę niże do "Sierpiński triangle" i zobacz obrazek. Ten automat zdefiniowany
jest banalną *lokalną* regułą na trzech sąsiednich komórkach jednowymiarowej tablicy,
i rozwija się iteracyjnie, linia po linii (to kolejne wartości całej tablicy). Jednak
w efekcie powstaje struktura, która *globalnie* kojarzy się nam z fraktalem. Trójkąt
Sierpińskiego można oczywiście zrobić rekurencyjnie, ale rekurencja wcale nie jest
potrzebna, żeby go zrobić. Podobnie jest z paprotkami. Właśnie dlatego upieram się,
że iteracja jest procesem naturalnym. Bo w naturze nie ma mechanizmu, który by
stworzył fraktal metodą rekurencyjną, natomiast lokalne procesy iteracyjne (np.
przyrost kolejnych wartstw komórek w roślinach) jak najbardziej są.

Rekurencja to nasz wymysł i propaganda. :-)

--
Maciej Sobczak * http://www.inspirel.com

do góry

> A procesy myślowe występują w naturze?

Występują. Ale na moje oko nie są rekurencyjne.
Tu wkraczamy na śliski teren, bo nie możemy udowodnić, że wszyscy myślą tak samo. Jak
się uprzesz, że myślisz rekurencyjnie, to nic na to nie poradzę. :-)

> Czy produkcja samochodów jest procesem występującym w naturze?

Tak. Raczej jest to proces iteracyjny.

> I dlaczego to miałoby być istotne?

Bo twierdzisz, że rekurencja jest *łatwiejsza* do zrozumienia. Łatwość czegokolwiek
jest subiektywna, ale jeśli małbym ją jakoś obiektywizować, to właśnie przez
odwołanie do natury. W sensie - jeśli jakieś zjawisko występuje w naturze, to czuję
się zupełnie racjonalnie, jeśli rozumiem je lepiej, niż jakieś inne zjawisko, któro w
naturze nie występuje.

Niemniej, jeśli się uprzesz, że myślisz inaczej (w sensie - inaczej, niż natura
chciała), to ja nie mam narzędzi, żeby dyskutować dalej. Będziemy musieli te nasze
różnice po prostu zaakceptować. :-)

> Jest zasadnicza różnica pomiędzy biologiczną reprodukcją, a obrotem
> słońca dookoła ziemi.

Ale deszcz jest z chmury, czy chmura z wody po deszczu? Co było wcześniej?
Dla mnie to jest cykl a nie jakaś rekurencja.

> Zauważ również, że w samym tym pytaniu manifestuje się
> myślenie rekurencyjne, czyli potrzeba ustalenia przypadku bazowego

Potrzeba ustalenia przypadku bazowego wynika tylko z tego, że rekurencja tego
potrzebuje (czyli jest to sztuczna potrzeba, tak jak rekurencja jest sztucznym
mechanizmem, wetkniętym tu na siłę). Natura wcale tego nie potrzebowała:

https://en.wikipedia.org/wiki/Emergence

Dla ludzi, którzy nie wpychają rekurencji wszędzie gdzie popadnie, nie jest to żadną
niespodzianką.

--
Maciej Sobczak * http://www.inspirel.com

do góry

W dniu czwartek, 4 stycznia 2018 10:52:07 UTC+1 użytkownik Maciej Sobczak napisał:
> > A procesy myślowe występują w naturze?
>
> Występują. Ale na moje oko nie są rekurencyjne.
> Tu wkraczamy na śliski teren, bo nie możemy udowodnić, że wszyscy myślą tak samo.
Jak się uprzesz, że myślisz rekurencyjnie, to nic na to nie poradzę. :-)

Otóż to ;)

> > Czy produkcja samochodów jest procesem występującym w naturze?
>
> Tak. Raczej jest to proces iteracyjny.

A wymyślanie algorytmów występuje w naturze? :)

> > I dlaczego to miałoby być istotne?
>
> Bo twierdzisz, że rekurencja jest *łatwiejsza* do zrozumienia.

Rzeczywiście w tej kwestii wyraziłem się nieprecyzyjnie, ale nie powiedziałem,
że rekurencja jest łatwiejsza do zrozumienia, tylko że jest prostsza
do zrozumienia.
Ale wycofałbym się z tego twierdzenia, bo ono jest niejasne.
Raczej powiedziałbym, że rekurencja jest pojęciowo prostsza, albo
bardziej pierwotna czy elementarna, niż iteracja.
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.

I w tym sensie iteracja jest prostsza od rekurencji, że ma mniejszą
siłę wyrazu (można przy jej pomocy zrobić mniej)

Na marginesie, pozwoliłem sobie wczorajużyć Twojej definicji przodka
w odpowiedzi na pytanie o funkcję "unfold":

https://www.quora.com/Why-is-an-unfold-function-usef
ul/answer/Panicz-Godek

> Łatwość czegokolwiek jest subiektywna,

Tak, łatwość jest subiektywna, ale prostota/złożoność nie jest.

> ale jeśli małbym ją jakoś obiektywizować, to właśnie przez odwołanie do natury. W
sensie - jeśli jakieś zjawisko występuje w naturze, to czuję się zupełnie
racjonalnie, jeśli rozumiem je lepiej, niż jakieś inne zjawisko, któro w naturze nie
występuje.

Ja uważam, że jest dokładnie na odwrót. W naturze występuje wiele
skomplikowanych zjawisk, które są niezgodne z intuicją. Na przykład
splątanie kwantowe, określone przez Einsteina, Rosena i Podolsky'ego
mianem "spooky action at a distance".

W naturze w ogóle nie ma czegoś takiego, jak zależności liniowe,
ale my je na siłę wpychamy do naszych analiz zjawisk naturalnych,
bo w taki sposób łatwiej nam rozumieć świat: toteż mamy na przykład
stałe przyspieszenie w polu grawitacyjnym Ziemi, albo siłę sprężystości
sprężyny liniowo proporcjonalną do wychylenia od "położenia naturalnego",
albo pojęcie "ruchu jednostajnego prostoliniowego".

> Niemniej, jeśli się uprzesz, że myślisz inaczej (w sensie - inaczej, niż natura
chciała), to ja nie mam narzędzi, żeby dyskutować dalej. Będziemy musieli te nasze
różnice po prostu zaakceptować. :-)

Moim zdaniem temat jest bardzo ciekawy, i wciąż ma duży potencjał
do dyskusji.
Wydaje mi się, że już z samym pojęciem natury jest pewien problem,
mianowicie taki, że trudno by było wskazać część świata, która
nie jest naturą. Z drugiej strony, czasem używa się go w tym celu,
żeby odróżnić to, co zostało zrobione przez człowieka (które są
"sztuczne") od pozostałych rzeczy (które są "naturalne").
Co więcej, nawet jeśli spojrzymy na język naturalny jako na wytwór
naturalny, to definicja - jako próba uchwycenia intuicji stojącej
za użyciem jakiegoś słowa - jest w jakimś sensie inherentnie
sztuczna. W tym oczywiście zarówno definicja rekurencyjna,
jak i iteracyjna.

Na przykład, mówi się o takim czymś, jak "liczby naturalne",
mając na myśli pewien konstrukt, który przychodzi ludziom do głowy
w sposób naturalny. Aksjomatyka Peano mówi tyle, że
- zero jest liczbą naturalną
- następnik liczby naturalnej jest liczbą naturalną

Pomijając kwestię tego, jak przełomowym osiągnięciem było wynalezienie
zera, i tego, że moglibyśmy używać liczb zupełnie nie zastanawiając się
nad tym, czym w istocie jest liczba, wydaje mi się, że trudno o prostsze
wyjaśnienie tego, czym jest liczba. I nie mam tutaj na myśli łatwości,
bo taka definicja rzeczywiście nie daje wskazówek odnośnie tego, dlaczego
liczby są użyteczne (np. do tego, żebyśmy mogli wiedziec, ile mamy krów,
albo czy obsiany areał wystarczy do tego, żeby wioska przetrwała zimę).

Zresztą, czy pytanie, czym są dane rzeczy, nie jest dla człowieka naturalne?

> > Jest zasadnicza różnica pomiędzy biologiczną reprodukcją, a obrotem
> > słońca dookoła ziemi.
>
> Ale deszcz jest z chmury, czy chmura z wody po deszczu? Co było wcześniej?
> Dla mnie to jest cykl a nie jakaś rekurencja.

To tylko woda zmieniająca stan skupienia. Woda, cały czas ta sama.

> > Zauważ również, że w samym tym pytaniu manifestuje się
> > myślenie rekurencyjne, czyli potrzeba ustalenia przypadku bazowego
>
> Potrzeba ustalenia przypadku bazowego wynika tylko z tego, że rekurencja tego
potrzebuje (czyli jest to sztuczna potrzeba, tak jak rekurencja jest sztucznym
mechanizmem, wetkniętym tu na siłę). Natura wcale tego nie potrzebowała:

Ja nie mówię o naturze, tylko o ludzkim myśleniu.

do góry

> 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.

> 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.

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.

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.

--
Maciej Sobczak * http://www.inspirel.com

do góry

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".

do góry

On Thu, 4 Jan 2018 01:36:35 -0800 (PST), Maciej Sobczak wrote:

>> A może weźmy pod uwagę fraktale? W naturze jest ich multum. Czy taki
>> przykład jest ok?
>
> W naturze nie ma fraktali. Ani jednego.

https://ciekawe.org/2015/11/02/fraktalne-wzory-w-prz
yrodzie/

I to wszystko nie ma nic wspólnego z fraktalami?

> Istnieją struktury, które były inspiracją albo wywołują jakieś
> skojarzenia fraktalowe, np. liść paproci. Ale problem w tym, że te
> struktury powstają iteracyjnie, dzięki zupełnie lokalnym procesom
> komórkowym, które o naszych rekurencyjnych skojarzeniach nic nie wiedzą.

Jak one powstają i co "wiedzą" to ja nie wiem, nie jestem botanikiem, a
nawet myślę, że i botanicy nie wszystko jeszcze wiedzą.

--
pozdrawiam
Roman Tyczka

do góry

> > W naturze nie ma fraktali. Ani jednego.
>
> https://ciekawe.org/2015/11/02/fraktalne-wzory-w-prz
yrodzie/
>
> I to wszystko nie ma nic wspólnego z fraktalami?

Przypomniał mi się taki dowcip:
Lekarz pokazuje pacjentowi jakiegoś kleksa na obrazku i pyta, co to jest. Pacjent
mówi, że goła baba. Lekarz pokazuje kilka kolejnych kleksów a pacjent dalej zeznaje,
że widzi gołe baby. Lekarz diagnozuje: panie, pan jesteś zboczony! A pacjent na to:
ja? a kto mi tu ciągle gołe baby pokazuje?

Polecam "New Kind Of Science" Wolframa albo od razu obrazki:

https://www.google.pl/search?q=new+kind+of+science+i
mages

To jest książka o wielu różnych ciekawych rzeczach (zwłaszcza dla programistów), ale
między innymi o tym, jak bardzo rekurencja nie jest potrzebna do zrobienia takich
wzorów.
Przykładowo, płatki śniegu, które były wspomniane w Twoim linku, nie rosną
rekurencyjnie, tylko przez *nawarstwianie*. Ten proces nie ma w sobie ani grama
rekurencji, bardziej przypomina ten wcześniejszy przykład z automatem tworzącym
kolejne warstwy z tablicy a w wyniku coś, co nam się kojarzy z trójkątem
Sierpińskiego.

Może taki argument się przyda: fraktale są strukturami w przestrzeni ciągłej (co
objawia się np. tym, że można je dowolnie powiększać). Takie nie są ani paprotka ani
brokuł ani płatek śniegu.

> myślę, że i botanicy nie wszystko jeszcze wiedzą.

Za to my wiemy lepiej od nich, co? :-)

--
Maciej Sobczak * http://www.inspirel.com

do góry

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

Ale ja do ich uruchomienia używam nie "istoty", tylko procesora. A tam iteracja
działa szybciej.

> Dobrze jest to wyjasnione w "Strukturze i Interpretacji Programów
> Komputerowych",

A jeszcze lepiej w dokumentacji procesora.

> Rekurencja natomiast zarówno może więcej (jest mniej wyspecjalizowana),
> jak również jest prostsza (w sensie złożoności) od iteracji.

Tego nie pokazałeś. Moja iteracyjna definicja przodka była prostsza od Twojej
rekurencyjnej. Moja iteracyjna metoda wyboru elementów z listy też była prostsza.

> W przypadku podanego przez Ciebie przykładu, zrozumienie zapisu x[[1 ;; ;; 2]]
> wymaga odwołania do dokumentacji

Tak.

> W rozwiązaniu Kaya jedyna przypadkowa złożoność
> jest w nazwach. Ale w tej kwestii z pomocą przychodzi nam dorobek
> Burstalla,

I teraz zrozumienie Twojego przykładu wymaga odwołania się do dorobku Burstalla. Nie
przekonałeś mnie, że jest to prostsze. A mój zapis dalej jest krótszy. Co więcej,
jeśli będę chciał mieć nie co drugi element, tylko co dziesiąty, to zmienię 2 na 10 i
działa: x[[1;; ;;10]]. Złożoność tego zapisu się nie zmieniła. Co musisz zmienić w
swoim przykładzie, żeby wybrać z listy co dziesiąty element?

--
Maciej Sobczak * http://www.inspirel.com

do góry