Dziennik elektroniczny     Facebook    Start    Kontakt   

Strona o programowaniu w języku LOGO

Procedury rekurencyjne

Rekurencja w nieskończoność

Definicja

Rekurencja to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie.

W logice wynik wnioskowania może podlegać tej samej regule zastosowanej ponownie.
Na prostym przykładzie:
Reguła: każdy ojciec jest starszy od swojego syna; każdy ojciec jest czyimś synem.
Teza: ojciec ojca mojego ojca jest starszy ode mnie.

Dowód:

1. mój ojciec jest starszy ode mnie
   
2. mój ojciec jest czyimś synem
   
3. ojciec mojego ojca jest starszy od mojego ojca
   
4. ojciec mojego ojca jest czyimś synem
   
5. itd.

---

Źródło:
http://pl.wikipedia.org/wiki/Rekurencja

 

W języku Logo zapis rekurencji będzie wyglądał następująco:

Tego typu procedura działa w nieskończoność. Przykładem takiej procedury, która się nie kończy nie będzie prosta procedura ruch.

To jest projekt Imagine zapisany dla WWW

Jeśli powyżej nie jest widoczna zawartość projektu, to należy zainstalować wtyczkę. Niestety nie działa ona prawidłowo z wersjami 64-bitowymi przeglądarek internetowych. Jednak możesz zainstalować na swoim komputerze 32-bitową wersję przeglądarki Opera i za jej pomocą oglądać udostępniane projekty.

W programie Logomocja zatrzymanie procedury, która działa w pętli następuje poprzez naciśnięcie przycisku F12.

Rekurencja zawierająca warunek zatrzymania

W większości przypadków jednak procedura rekurencyjna powinna się kiedyś zakończyć.

Zasadę działania procedury rekurencyjnej można opisać w następujący sposób: wykonaj pewne operacje, dalej wykonuj te same operacje dla zmienionych parametrów. Wykonuj operacje tak długo aż nastąpi warunek zakończenia działania procedury.

Dlatego przygotowując procedurę rekurencyjną należy zadbać o istnienie warunku zatrzymującego wykonywanie procedury. Skorzystaj w tym celu z procedury warunkowej jeśli. Ma ona następującą strukturę:

jeśli wartość logiczna lista-P

Jeśli dana jest wartość logiczna prawda, wykonywana jest dana lista poleceń. W przeciwnym przypadku, nie robi się nic i koniec - polecenie nie ma żadnego skutku.

Spirala

Przykładem procedury rekurencyjnej, którą można spotkać w wielu podręcznikach jest właśnie spirala.
Jak powstaje spirala? Spróbuj narysować ją poprzez poruszanie się żółwiem do przodu za każdym razem zmniejszając krok o 2 punkty aż do 0.

Poniżej możesz zobaczyć wykonanie procedury spirala.R z parametrem 200.

Parkiet

Żółw rysując parkiet działa następująco:
Rysuj kwadrat zamalowany losowym kolorem – zwróć uwagę, że do narysowania kwadratu użyto polecenia wielokąt a nie kombinacji poleceń np i pw – dzięki temu jest on zamalowany.
Dalej wykonuj rysowanie kwadratu dla boku zmniejszonego o 20.
Jeśli parametr :bok będzie mniejszy lub równy 0 zatrzymaj procedurę.

Poniżej wykonanie procedury parkiet z parametrem 200.

Zadania do samodzielnego wykonania

Jescze raz spirale.
Spróbuj zmodyfikować procedurę spirala.R przez dodanie parametru określającego kąt obrotu żółwia zamiast kąta 90 stopni. Procedurę oraz wyniki jej wywołania możesz zobaczyć poniżej.

Zwróć uwagę, że kąt 122 wybrano nieprzypadkowo 3*122=366, a więc kąt o 6⁰ większy od kata pełnego - dzięki temu uzyskano ciekawy efekt wachlarza.

---

Jak wykonano poniższe spirale?

SPONSORZY

ING BAnk Śląski SA
Oddział w Katowicach
5 komputerów polizingowych 2008

---

MEN oraz Europejski Fundusz Społeczny Projekt „Pracownie komputerowe dla szkół” rok 2005

---

Urząd Miasta Łziska Górne
Pracownia 10 komputerów rok 2002