Silnia

Zacznijmy od algorytmu wyznaczania silnisilniasilni z liczby naturalnej. Zastosujemy w pseudokodzie rekurencję – funkcja będzie wywoływała samą siebie aż do momentu dojścia do przypadku podstawowegoprzypadek podstawowyprzypadku podstawowego. Przy pisaniu pseudokodu pomocna okaże się definicja rekurencyjna silni.

Zgodnie z tą definicją funkcja będzie wywoływała samą siebie z parametrem zmniejszonym o 1, aż do momentu, gdy n będzie równe 0 – wtedy zostanie zwrócona wartość 1. Pseudokod funkcji rekurencyjnej realizującej algorytm wyznaczania silni liczby naturalnej n wygląda następująco:

funkcja silnia(n)
	jeżeli n == 0 wykonaj:
    	zwróć 1
    w przeciwnym razie wykonaj:
    	zwróć silnia(n-1) * n

Najpierw będą rekurencyjnie wywoływane funkcje z coraz mniejszymi wartościami, czyli 5, 4, 3, 2, 1, aż dojdziemy do 0. Wtedy nastąpi zwrócenie wartości 1 i zaczniemy po kolei wychodzić z zagnieżdżenia wywołań funkcji, za każdym razem zwracając wynik danej silni. Na koniec osiągniemy szukaną wartość 6!:

R123ixfSk5c87

Ilustracja przedstawia tabelę o nagłówkach: n oraz silnia(n).
Pod n wypisano liczby: 6, 5, 4, 3, 2, 1, 0.
Pod silna(n): 720, 120, 24, 6, 2, 1, 1.
W kolumnie n znajduje się strzałka skierowana do dołu , a w kolumnie silnia(n) do góry.

Wyraz ciągu rekurencyjnego

Rozpocznijmy od warunku, który mówi o tym, że dla n mniejszego od 2 zwracana jest wartość 122.

funkcja funkcja(n)
	jeżeli n < 2 wykonaj:
    	zwróć 122

Natomiast jeżeli n NIE JEST mniejsze od 2, musimy sprawdzić, czy n jest liczbą parzystą, i umieścić odpowiednie instrukcje w przypadku spełnienia tego warunku.

funkcja funkcja(n)
	jeżeli n < 2 wykonaj:
    	zwróć 122
    w przeciwnym razie wykonaj:
    	jeżeli n % 2 == 0 wykonaj:
        	zwróć funkcja(n‑2) - 3

Jeżeli n nie jest liczbą parzystą, musimy zwrócić funkcja(n‑1) mod 9.

funkcja funkcja(n)
	jeżeli n < 2 wykonaj:
    	zwróć 122
    w przeciwnym razie wykonaj:
    	jeżeli n % 2 == 0 wykonaj:
        	zwróć funkcja(n‑2) - 3 
        w przeciwnym razie wykonaj:
        	zwróć funkcja(n‑1) mod 9

Zapisaliśmy za pomocą pseudokodu funkcję zwracającą n‑ty wyraz ciągu rekurencyjnego.

Funkcja wywołuje samą siebie we wszystkich przypadkach poza tymi, kiedy n = 0 lub n = 1. Na przykład funkcja(5) wywołuje funkcję funkcja(4). Nie musimy jednak ponownie wyznaczać wartości tej funkcji, ponieważ obliczyliśmy ją w poprzednim kroku.

Ciąg rekurencyjny

Przeanalizujmy przedstawioną za pomocą pseudokodu funkcję ciąg(x, y) przyjmującą parametry x i y typu całkowitego, której wywołanie spowoduje wypisanie ciągu liczb całkowitych:

funkcja ciąg(x, y)
	jeżeli y > 0 wykonaj:
    	ciąg(2*x, y-1)
        ciąg(3*x, y-2)
        wypisz x - y

Do wykonania tego zadania pomocne okaże się drzewo wywołań rekurencyjnych, w którym umieścimy wszystkie wywołania funkcji ciąg(2, 4).

RnSB7aDOaIbrb

ilustracja przedstawia drzewo wywołań rekurencyjnych.
1: ciąg(2, 4), 2: strzałka wprawo: ciąg(6, 2) 3: strzałka do dołu: ciąg(12, 1), 2: strzałka w lewo: ciąg(4, 3), 3: strzałka w prawo: ciąg (12, 1), 3: strzałka w lewo: ciąg(8, 2), 4: strzałka w dół: ciąg (16, 1)

W drzewie zostały przedstawione wywołania tylko tych funkcji, których wartość drugiego przyjmowanego argumentu, czyli y, jest większa od 0. Z tego względu wykonania niektórych funkcji powodują wywołanie tylko jednej rekurencyjnej funkcji. Lewa strzałka każdej z funkcji prowadzi do wywołania funkcji ciąg(2*x, y‑1), natomiast prawa prowadzi do ciąg(3*x, y‑2).

Ponownie skorzystamy z drzewa wywołań rekurencyjnych. Wiemy, że nasz ciąg to uzyskane wartości działań x - y. Jednak w jakiej kolejności wypisywane są te wartości? Spójrzmy ponownie na zapisaną za pomocą pseudokodu funkcję ciąg(x, y). Najpierw zostanie wywołana rekurencyjnie funkcja ciąg(2*x, y‑1), czyli lewa skierowana krawędź, następnie ciąg(3*x, y‑2), czyli prawa krawędź, a na końcu wypisana zostanie wartość x - y.

A zatem początek wygenerowanego ciągu rekurencyjnego zgadza się z naszymi wnioskami. W pierwszej kolejności wykonywane jest najniżej położone, lewe poddrzewo, zatem wywołana zostanie funkcja ciąg(16, 1).

Następnie miałoby zostać wykonane prawe poddrzewo, jednak takie nie istnieje, przechodzimy więc do wyższego poziomu, czyli ciąg(8, 2). Stosując powyższe obserwacje, uzyskamy następujący ciąg:

Słownik