Algorytmy i Programowanie - Ćwiczenia 5

Temat: Debugowanie. Rekurencja.

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:

F8 - przejście do następnej linii.
F7 - przejście do następnej linii, chyba, że jest to procedura lub funkcja, wtedy przejście do pierwszej linii tej procedury/funkcji.
F4 - przejście do wskazanej kursorem linii.
F9 - przejście do trybu normalnego działania programu (bez wykonywania linia po linii).
CTRL + F5 - dodanie zmiennej wskazanej kursorem do Watcha.
CTRL + F2 - zakończenie działania programu.

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;

Zadanie

Przy pomocy programu używającego rekurencji, wyznacz n-tą liczbę Fibbonacciego.

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

Zadanie

Zadanie 1260 na timusie

Rozwiązaniem tego zadania jest wynik rekurencji zadanej wzorem:
B(1)=1
B(2)=1
B(3)=2
B(n)=B(n-1)+B(n-3)+1
Ze względu na ograniczenie czasowe zadanie należy zrobić w sposób iteracyjny (bez rekurencji, przy pomocy wypełniania tablicy)