Rekurencja

"Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) – odwoływanie się np. funkcji lub definicji do samej siebie.

W logice wnioskowanie rekurencyjne opiera się na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym, aby cały dowód był poprawny, zarówno reguła, jak i stan początkowy muszą być prawdziwe). Istotą rekurencji jest tożsamość dziedziny i przeciwdziedziny reguły wnioskowania, wskutek czego wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie."
"Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Ryzyko istnieje szczególnie przy przetwarzaniu dużej ilości głęboko zagnieżdżonych danych."

Z Wikipedii

W praktyce rekurencja sprowadza się do wielokrotnego wywoływania funkcji przez samą siebie, coraz bardziej "w głąb stosu", dla coraz mniej skomplikowanego zadania, aż dochodzimy do trywialnej jego wersji i dalsze zagłębianie się nie ma już sensu. 

Rekurencja jest przez teoretyków programowania uznawana za samo sedno inteligencji algorytmicznej. Wg. nich nie jest programistą ten kto rekurencji nie rozumie ;-)
Ja nie byłbym tak ortodoksyjny, ale jednak uważam, że warto tą ideę wytłumaczyć, bo bez tego trudno o zrozumienie grafik fraktalnych, które są po prostu ładne :-)

Temat rekurencji wprowadza się zwykle za pomocą funkcji silni czy jakiś ciągów - np. Fibbonacciego. Ale to czysta matematyka, a ja w tym kursie staram się używać raczej grafiki, jako trafiającej do większej liczby odbiorców.
W grafice komputerowej raczej unika się algorytmów rekurencyjnych, jako mało efektywnych, ale istnieje jeden, historycznie istotny. To "wypełnianie przez sianie" czy też, wg. bardziej popularnej nazwy angielskiej "flood fill".
Niestety algorytm ten wymaga możliwości odczytania koloru punktu, który już jest na ekranie (czy w oknie), której jednak w Processingu nie znalazłem. Jest taka, która pozwala czytać kolor punktu załadowanego obrazka, co może kiedyś jeszcze wykorzystamy.

Dla ilustracji prostej graficznej procedury rekurencyjnej użyjemy procedury rysującej linię przerywaną. Jest ona oczywiście bardzo nieefektywna i do wymagających obliczeniowo zadań się nie nadaje, ale dydaktycznie powinna być wystarczająca.

Wynikiem działania programu będą czarne kropki naniesione wzdłuż dowolnego odcinka prostej. Ich gęstość może być różna. Na obrazki limit gęstości wynosi 10. Żółte tło pod kropkami stanowi "kontrolę" narysowaną zwykłą funkcją line()  Processingu.

Moglibyśmy te kropki oczywiście narysować też za pomocą pętli. Większość algorytmów rekurencyjnych da się zmienić na klasyczne, choć zapis rekurencyjny jest zazwyczaj dużo prostszy.
Oto kompletny program:


Funkcja setup() służy nam jak zwykle do ustawień, oraz do pierwszego wywołania naszej rekurencyjnej funkcji bline() (linia 12.) i narysowania kontrolnej linii klasycznym algorytmem (linia 11.). Funkcji draw() nie implementujemy bo jest w tym teście niepotrzebna.

Sama funkcja jest dosyć prosta. Najpierw sprawdzamy czy zadany odcinek jest wystarczająco długi żebyśmy chcieli postawić w nim kropkę (linie 17-20). Długość liczymy po prostu jako odległość Euklidesa między punktami.
Potem obliczamy współrzędne punktu leżącego pośrodku odcinka wyznaczonego przez parametry wywołania. Kolejność dalszych operacji jest dowolna. U mnie najpierw następują rekurencyjne wywołania dla obu połówek odcinka, a potem dopiero zaznaczenie punktu środkowego za pomocą point(), ale równie dobrze można zrobić odwrotnie.
Każde zatem wywołanie rysuje jeden punkt i próbuje narysować kolejne używając wywołania tej samej funkcji. Za zakończenie tego procesu odpowiada zmienna limit (linia 4.)

Jeśli zrozumiecie jak to działa, kolejne programy, rysujące znane fraktale będą dla was dużo bardziej zrozumiałe.