Funkcje rekurencyjne
Funkcja rekurencyjna to taka funkcja, która zawiera wywołanie samej siebie. Użycie funkcji rekurencyjnej
pozwala zapisać wiele algorytmów w czytelnej i często bardzo prostej formie. W tym rozdziale przedstawimy
typowe cechy funkcji rekurencyjnych oraz jak taką funkcję zaprogramować w POOL.
- Obliczanie silni
- Proste fraktale
- Rekurencja wzajemna
- Ciąg Fibonacciego
Obliczanie silni
Silnia liczby naturalnej n to iloczyn wszytkich liczb naturalnych nie większych niż n:
n! = 1 * 2 * 3 * ... * n. Na przykład:
5! = 1 * 2 * 3 * 4 * 5 = 120. Rekurencyjny algorytm silni można zapisać jako:
a) n! = n * (n - 1)! jeśli n > 1
b) n! = 1 jeśli n ≤ 1
Zauważ: każdy algorytm rekurencyjny potrzebuje warunku zakończenia działania. Algorytm w
punkcie a) oblicza silnię jako iloczyn liczby i silni tej liczby pomniejszonej o 1. Ten ciąg obliczeń
kończy się gdy bieżąca wartość n osiągnie 1 i zostanie spełniony warunek z punktu b).
Rekurencyjna implementacja silni w POOL wygląda następująco:
to silnia :n
print :n
if :n <= 1 [output 1]
output :n * silnia :n - 1
end
(print "wynik silnia 5)
Wynik działania programu (w oknie tekstowym):
5
4
3
2
1
wynik 120
Funkcja silnia
posiada jeden argument: liczbę n, a jako wynik zwraca wartość n!.
Sposób zdefiniowania takiej funkcji opisaliśmy już w poprzednim rozdziale.
Tu pojawia się po raz pierwszy instrukcja warunkowa: if
.
Pozwala ona wykonać blok kodu umieszczony w liście (tu: output 1
)
tylko jeśli spełniony jest warunek podany w pierwszym argumencie instrukcji (tu:
:n <= 1
).
Dla zilustrowania kolejności obliczeń funkcja silnia
w każdym wywołaniu wypisuje wartość argumentu
:n
. Zauważ, że pojedyńcze wywołanie silnia 5
powoduje wypisanie liczb od 5 do 1. Dzieje
się tak dlatego, że funkcja wywołuje samą siebie dla kolejnych wartości aż do 1. Wiąże się z tym
ważna cecha
funkcji rekurencyjnych
: w czasie wykonania funkcji w pamięci przechowywane są argumenty i zmienne lokalne
wszystkich rekurencyjnych wywołań funkcji. Ilość pamięci potrzebna do wykonania funkcji rekurencyjnej może być
istotnym czynnikiem podczas programowania algorytmu. Należy wtedy pomyśleć nad standardowym, nierekurencyjnym
odpowiednikiem. W przypadku silni może to być np. taka funkcja:
to silnia_1 :n
if :n <= 1 [output 1]
let "k :n
while :n > 2 [
"n := :n - 1
"k := :k * :n
]
output :k
end
Ta funkcja używa dwóch zmiennych: argumentu :n
i zmienej lokalnej :k
do obliczenia
silni z dowolnej wartości.
Proste fraktale
Używając funkcji rekurencyjnych łatwo można zaprogramować rysowanie fraktali - figur, których mniejsze fragmenty
są podobne do większych części lub całej figury. Poniżej przedstawiamy dwa przykłady wybrane z projektu
fraktale cz.I.
Płatek Kocha
Zacznijmy od prostej funkcji:
to k1 :r
fd :r/3 rt 60
fd :r/3 lt 120
fd :r/3 rt 60
fd :r/3
end
Pojedyńcze wywołanie k1
rysuje bok figury o rozmiarze :r
, jak na rysunku po lewej.
Sześciokrotne powtórzenie z obrotem dopełnia figurę, jak na rysunku po prawej.
repeat 6 [k1 90 rt 60]
Teraz prosta zmiana: każdy krok fd :r/3
zamieniamy na rekurencyjne wywołanie koch :r/3 :g-1
,
w którym jednocześnie zmniejszamy licznik wywołań :g
; warunkiem przerwania rekurencji jest
:g = 0
:
to koch :r :g
if :g = 0 [fd :r stop]
koch :r/3 :g-1 rt 60
koch :r/3 :g-1 lt 120
koch :r/3 :g-1 rt 60
koch :r/3 :g-1
end
repeat 6 [koch 90 5 rt 60]
Drzewo
Drzewo to inny popularny rodzaj fraktala. Modyfikując poniższy program można otrzymać różne formy. Także liście
paproci umieszczone w projekcie należą do tej kategorii rysunków.
to drzewo :r :g
if :g > 0 [
setpensize :g
fd :r
lt 20
drzewo :r * 0.7 :g - 2
rt 40
drzewo :r * 0.9 :g - 1
lt 20
pu bk :r pd
]
end
drzewo 100 15
Rekurencja wzajemna
Dwie niezależne funkcje mogą wywoływać się nawzajem, jak w poniższym przykładzie krzywej Wirth'a:
to wi :n :a :h :k
if :n = 0 [fd :h stop]
rt :a iw :n (-:a) :h :k lt :a fd :h
lt :a iw :n (-:a) :h :k rt :a
end
to iw :n :a :h :k
rt :a wi :n - 1 (-:a) :h :k fd :k lt 2 * :a
fd :k wi :n - 1 (-:a) :h :k rt :a
end
to wirth :n :s
repeat 4 [
wi :n 45 3*:s :s
fd :s rt 90 fd :s
]
end
ht wirth 4 2
Rekurencja tego rodzaju zawsze może zostać zamieniona na pojedynczą funkcję rekurencyją wi
przez
zastąpienie wywołań iw
kodem tej funkcji, choć otrzymany w ten sposób kod może być mniej przejrzysty.
Wzajemna rekurencja jest stosowana w praktyce w parserach stosujących rekurencyjnie
analizę zstępującą składni.
Ciąg Fibonacciego
Często przytaczanym podstawowym przykładem zastosowania rekurencji jest obliczanie kolejnych elementów ciągu
Fibonacciego. Liczby w tym ciągu to f0 = 0, f1 = 1,
fn = fn-1 + fn-2.
Rekurencyjna funkcja może wyglądać następująco:
to fibo_rec :n
if :n < 2 [output :n]
output (fibo_rec :n-2) + (fibo_rec :n-1)
end
Choć funkcja jest bardzo prosta, to już dla elemtów ciągu o numerze 30-40 czas obliczeń rekurencyjnych jest
zauważalny... dzieje się tak dlatego, że jedno wywołanie funkcji w programie powoduje dwa wyołania rekurencyjne,
które z kolei wywołują po dwa razy funkcję itd, aż do sumarycznej liczby wywołań 331160281 dla n = 40.
W tym przypadku algorytmiczny odpowiednik rekurencji jest bardzo pomocny, spróbuj poniższej funkcji:
to fibo_alg :n
if :n < 2 [output :n]
let "n2 0
let "n1 1
let "nx 0
repeat :n-1 [
"nx := :n2 + :n1
"n2 := :n1
"n1 := :nx
]
output :nx
end
Dla ciągu Fibonacciego, jak dla każdego ciągu, w którym elementy są określone przez liniową kombinację
wcześniejszych elementów ze stałymi współczynnikami, można podać wzór na n-ty element. Ten sposób
obliczeń jest ostatecznie najbardziej wydajny:
to fibo_mat :n
output round ((0.5 * (1 + sqrt 5))^:n) / (sqrt 5)
end
Istnieje także uogólniona wersja ciągu Fibonacciego dla liczb zespolonych. Można go przedstawić na
płaszczyźnie liczb zespolonych kolorując punkty według algorytmu escape time, używanego często
w rysowaniu fraktali - wynikiem są obrazy jak ten przedstawiony poniżej (również wykonany w POOL). Jednak
temat ten zostawiamy na osobny artykuł.