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.


Przykład rekurencji
w sztuce użytkowej
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:

oto nazwa_procedury
 czynności_wykonywane_przez_procedurę
 nazwa_procedury
już

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.

oto starter
 usuńobiekt wszystkie
 nowy "żółw [nazwa piesek postać pies kierunek 90 pisak pod poz [0 0]]
 słuchaj "piesek
 ruch
już

oto ruch
 np 2 czekaj 10
 ruch
już

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.

oto spirala.R :bok
 jeśli :bok < 0 [stop]
 np :bok pw 90
 spirala.R :bok - 2
już

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

oto parkiet :bok
 jeśli :bok <= 0 [stop]
 ukm jld
 wielokąt [4 [:bok 90]]
 parkiet :bok - 20
 już

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.

oto spirala.R :bok :kąt
 jeśli :bok < 0 [stop]
 np :bok pw :kąt
 spirala.R :bok - 2 :kąt
już

spirala 200 122

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


Jak wykonano poniższe spirale?

Valid XHTML 1.0 StrictPoprawny CSS!
Copyright (c) 2009-2017. Szkoła Podstawowa nr 3 im. Mikołaja Kopernika. All rights reserved.