Algorytmy i Programowanie - Ćwiczenia 5

Poprzednie Następne
Temat: Rekurencja. Debugowanie

Rekurencja

Charakterystyczną cechą funkcji (procedury) rekurencyjnej jest to, że wywołuje ona samą siebie. Drugą cechą rekursji jest jej dziedzina, którą mogą być tylko liczby naturalne.
Funkcja rekurencyjna przeważnie opiera się na pewnym wzorze, w którym po obu stronach równości występuje ta sama funkcja obliczana dla różnej wielkości parametru. Oprócz tego w każdej funkcji rekurencyjnej niezbędny jest tzw. "warunek początkowy", dzięki któremu wartość funkcji można obliczyć.
Najłatwiej zrozumieć mechanizm działania rekursji na przykładzie silni.

Silnia

Matematyczna definicja silni wygląda następująco:
n!=\begin{cases} 1 & \mbox{ dla }n=0 \\ n(n-1)! & \mbox{ dla }n\ge1 \end{cases}
Jak widać, silnia zdefiniowana jest niemal przez samą siebie. Do tego mamy zdefiniowany warunek początkowy: 0! = 1;
Czyli aby obliczyć 4! trzeba najpierw obliczyć 3! i wynik pomnożyć przez 4. Żeby obliczyć 3! trzeba obliczyć 2!. Żeby z kolei to obliczyć trzeba znać 1!, do obliczenia którego jest potrzebne 0!, którą to liczbę znamy, bo jest nią 1. Zatem teraz cofając się z tym rozumowaniem i podstawiając kolejne wartości mamy:
1! = 1*1 = 1;  
2! = 2*1! = 2*1 = 2;  
3! = 3*2! = 3*2 = 6;
4! = 4*3! = 4*6 = 24;

Rekurencja c.d.

Funkcje rekurencyjną często można zamienić na zwykłą funkcję iteracyjną. Np. w przypadku silni oczywiście wiemy, że n! = n(n-1)(n-2)...2*1. Można to łatwo wyliczyć przy pomocy zwykłej pętli. I jeśli tylko można należy rekurencji unikać, gdyż funkcje rekurencyjne mają przeważnie dużą złożoność obliczeniową, a ponadto wymagają zastosowania wewnętrznego stosu.
Niemniej często nie da się zrobić czegoś bez rekurencji, więc jest to narzędzie bardzo przydatne, które warto znać.

Debugowanie

Szukając błędu, sprawdzając, czy program dobrze działa, albo po prostu z ciekawości, można obserwować jak program się wykonuje krok po kroku. Aby to zrobić należy uruchomić program zamiast przyciskiem Run (F9, zielony trójkat PLAY), przyciskiem STEP OVER (nieco na prawo od Run, albo F8). Program będzie wykonywany krokowo, linia po linii. W edytorze kodu pojawi się zielona strzałka, wskazująca aktualnie wykonywaną instrukcję. Proces wykonywania programu linia po linii w celu wyszukania błędu w kodzie nazywa się debugowaniem. W trakcie tego procesu można podglądać zmieniające się wartości poszczególnych zmiennych. Można to zrobić poprzez najechanie myszką na zmienną w kodzie, bądź poprzez tzw. watch, czyli miejsce, gdzie wyświetlane są wartości zmiennych.
Do wykonywania instrukcji krok po kroku mogą przydać się następujące operacje: