Rekurencja

Technika

Rekurencja jest to technika programowania, która polega na tym, że funkcja wywołuje samą siebie w celu zrealizowania zadania. Rekurencja jest prawidłowo napisana tylko pod warunkiem, że kiedyś się zakończy. W informatyce można ją znaleźć w implementacji drzew binarnych lub podczas rysowania fraktali. (Chociaż i w tym przypadku ogranicza się rysowanie fraktali.)

Przykład

Dotychczas wypisywanie listy polegało na wykorzystaniu pętli. Dla każdego elementu wywoływany był ten sam zestaw instrukcji. Rozwiązaniem takiego polecania byłby poniższy kod:

1. void wypiszListaItr(int* lista, int n) {
2.   for (int i = 0; i < n; i++) {
3.     cout << lista[i] << " ";
4.   }
5. }

Zadanie to można sformułować inaczej. Jeżeli podana lista nie jest pusta to wypisz pierwszy element, usuń go z listy i wypisz powstałą listę. Zapis krokowy funkcji wypiszLista() byłby następujący zestaw instrukcji. Rozwiązaniem takiego polecania byłby poniższy kod:

1. Jeśli podana lista jest pusta to przerwij działanie funkcji
2. Wypisz pierwszy element z podanej listy
3. Usuń wypisany element z listy
4. Wywołaj funkcję wypiszLista() jeszcze raz z nową listą

W tym przypadku rekurencja ma spełnione wszystkie założenia z definicji. Napisana funkcja odwołuje sie do samej siebie. Ponadto funkcja ma warunek stopu jakim jest sprawdzenie czy lista jest pusta. Warto zauważyć, że jest to poprawny warunek stopu, ponieważ po każdym wywołaniu funkcja dostaje listę mniejszą o 1 element.

Implementacja

Wypisywanie elementów

Funkcja może przyjmować dodatkowy argument i, który wskaże, który element listy funkcja ma wypisać. Innymi słowy zadanie będzie korzystać z indeksu jak w pętli, ale nie będzie to przeczyć rekurencji. Poniżej znajduje się odpowiedni przykład:

1. void wypiszListaRek(int* lista, int n, int i = 0) {
2.   if (i >= n)
3.     return;
4.   cout << lista[i] << " ";
5.   wypiszListaRek(lista, n, i + 1);
6. }

(1.) Funkcję można wywołać tak samo jak wersję iteracyjną: podając tylko wskaźnik na tablicę lista oraz jej długość n. Trzeci argument i jest opcjonalny. (2.) Warunkiem (3.) stopu jest wyjście indeksu poza jego prawidłowe wartości. Jednak jeśli indeks jest prawidłowy to: (4.) należy wypisać i-ty element, a potem (5.) wywołać funkcję z tą samą listą i jej długością, ale z zwiększonym indeksem.

Po uruchomieniu program dla listy {1, 2, 3, 4, 5} wypisze na ekran:

1. 1 2 3 4 5

Wypisywanie elementów wspak z indeksem

W celu wypisania elementów wspak podczas korzystania z pętli wystarczyło zacząć od największego indeksu i skończyć na indeksie 0. W przypadku rekurencji istnieje możliwość zastosowania tego, ale należy pamiętać, że argument opcjonalny nie może przyjąć wartości innego argumentu. Wtedy należałoby dopisać przeciążenie funkcji tak, aby podała argument i jako n - 1.

1. void wypiszListaRekWspak1(int* lista, int n) {
2.   wypiszListaRekWspak1(lista, n, n - 1);
3. }

Zmiana kierunku wypisywania danych powoduje, że należy zmienić warunek stopu na i < 0. Ponadto w trakcie wywoływania funkcji należy podczas kolejnego wywołania zmniejszyć indeks, a nie zwiększyć. Po uruchomieniu program dla listy {1, 2, 3, 4, 5} wypisze na ekran:

1. 5 4 3 2 1

Wypisywanie elementów wspak

Taka implementacja nie jest zbyt wygodna, a istnieje jej prostszy odpowiednik, który wymaga jedynie zmiany linijek w pierwszej implementacji. Mianowicie w celu wypisania elementów wspak wystarczy zamienić linijki (4.) i (5.). Wtedy kod będzie wyglądał następująco:

1. void wypiszListaRekWspak2(int* lista, int n, int i = 0) {
2.   if (i >= n)
3.     return;
4.   wypiszListaRekWspak2(lista, n, i + 1);
5.   cout << lista[i] << " ";
6. }

To jest miejsce w którym wiele osób ma problemy ze zrozumieniem. Istotą tego problemu jest zrozumienie jaka jest różnica pomiędzy ustawieniem wykonania zestawu instrukcji, a ponownym wywołaniem funkcji. W poniższej tabeli zostało pokazany ślad wywołania dla obu kodów dla listy L = {1, 2, 3}.

Jak można zauważyć w drugim przypadku wcześniejsze elementy są wypisywane po dalszych i właśnie na tej podstawie działa przedstawiony kod.

Błędy implementacji

Błędne umieszczenie warunku stopu

Bardzo częstym błędem jest niewłaściwe umiejscowienie warunku stopu tak jak na poniższym przykładzie:

1. void wypiszListaRek(int* lista, int n, int i = 0) {
2.   wypiszListaRek(lista, n, i + 1);
3.   if (i >= n)
4.     return;
5.   cout << lista[i] << " ";
6. }

W powyższym przykładzie wywołanie rekurencyjne jest wykonywane przed sprawdzaniem warunku co powoduje, że wywoływanie funkcji jest zapętlone w nieskończoność, więc nie jest spełniony warunek o skończoności algorytmu. Tego typu błąd prowadzi do przepełnienia stosu (ang. stack overflow).

Błędny warunek stopu

Drugim poważnym błędem popełnianym podczas pisania rekurencyjnym jest błędny warunek stopu lub jego całkowity brak. Powoduje to, że program może działać w nieskończoność (i doprowadzić do przepełnienia stosu) lub wykonać tylko część zadania.

W celu lepszego zrozumienia po co jest potrzebny warunek warto przeanalizować poniższy algorytm na mycie włosów:

1. Nałożyć szampon na włosy, spłukać
2. Czynność powtórzyć

Nieprawidłowe zapętlenie

Nie dotyczy to tylko rekurencji, ale również. Niemniej ze względu na to, że wiele osób nie czuje rekurencji to bardzo często dochodzi do pomyłki, której nie popełniliby podczas pisania pętli. Jeden z takich przykładów dotyczy wypisywania co drugiego wyrazu podanej listy tak jak poniżej:

1. void wypiszListaRekCo2(int* lista, int n, int i = 0) {
2.   if (i == n)
3.     return;
4.   cout << lista[i] << " ";
5.   wypiszListaRek(lista, n, i + 2);
6. }

Powyższy przykład działa prawidłowo tylko w przypadku, gdy lista ma parzystą ilość elementów. W innym przypadku rekurencja pozostanie nieskończona, ponieważ i zawsze będzie różne od n. Innym nieprawidłowym zapętleniem jest niedoprowadzenie do momentu, gdy warunek stopu nigdy nie zostanie osiągnięty.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję o nagłówku void wypiszListaRekWspak(int* lista, int n), która wypisze w sposób rekurencyjny elementy wspak na liście lista. Liczby powinny być rozdzielone znakiem przerwy " ". Uwaga: nie wolno dopisać żadnej dodatkowej funkcji.

Zadanie 2

Wskaż, dlaczego algorytm polegający na cofnięciu zegarków o godzinę z 03:00 na 02:00 mógłby nie zadziałać poprawnie i zastanów się jak należałoby podejść do takiego zadania.

Odpowiedź

• Kod źródłowy Zadanie 1