Strona główna » Algorytmy » Artykuły » Rekurencja Ogonowa
 

Rekurencja Ogonowa

https://mattomatti.com/a0194

Wstęp

Rekurencja pozwala napisać większość algorytmów w kilku linijkach, ale nie zawsze jest to optymalna metoda. Może jednak taką się stać jeśli zwykłą rekurencją uda się przepisać w rekurencję ogonową.

Rekurencja

Rekurencja, podobnie jak pętla posiada pewne instrukcje do wykonania przy każdym wywołaniu oraz warunek stopy, który spowoduje, że program przejdzie do kolejnych instrukcji. Jednak dużo osób mylnie twierdzi, że pomiędzy dwoma stylami pisania algorytmu nie ma żadnej znaczącej różnicy. Otóż program wywołując funkcję musi wiedzieć jak wrócić do poprzedniego wywołania. To z kolei powoduje, że musi na stosie zapisać sobie ten adres oraz kilka innych wartości. Oznacza to, że każdym wywołaniem funkcji stos jest coraz większy.

Jak można się spodziewać im bardziej stos rośnie tym więcej potrzebuje miejsca w pamięci. Czasem program potrzebuje zapisać tyle powrotów, że zostaje przerwany przez system z powodu braku pamięci. Co więcej należy pamiętać, że program w którym nie wystąpi błąd musi później zakończyć pracę wracając po każdym zapisanym adresie w pamięci. Można jednak zapisać rekurencję w postaci tzw. ogonowej.

Postać ogonowa nakłada dwa podstawowe warunki na funkcję: może być tylko jedno wywołanie rekurencyjne w kodzie oraz, że jest ono na samym końcu funkcji. Inaczej mówiąc funkcja zapisana jako rekurencja ogonowa musi na końcu zwracać wynik kolejnego wywołania. Wyniku kolejnego wywołania nie można modyfikować, więc należy dodatkowo utworzyć akumulator czyli dodatkowe miejsce w pamięci, które pozwoli na przechowywanie aktualnego wyniku, który na sam koniec zostanie zwrócony.

Implementacja

Rekurencja

Przejdźmy do zapisania funkcji do obliczania silni. Podstawowa, rekurencja wersja wygląda następująco:

  1. int silniaRek(int n) {
  2.   if (n == 0) {
  3.     return 1;
  4.   }
  5.   return n * silniaRek(n - 1);
  6. }

Nie jest to rekurencja ogonowa, ponieważ należy pozbyć się mnożenia przez n w ostatniej linijce (możemy tylko zwrócić wynik kolejnego wywołania). Z kolei liczony wynik powinien zostać przechowany w oddzielnym miejscu tj. akumulatorze.

Rekurencja Ogonowa

Akumulator zazwyczaj jest to dodatkowa zmienna opcjonalna o pewnej początkowej wartości. Tutaj ze względu na fakt, że w każdej iteracji akumulator będzie mnożony przez kolejne liczby naturalne to początkowo musi przyjąć wartość 1. Z kolei mnożenie przez n zostanie przesunięte do wnętrza wywołania funkcji. Oto kod:

  1. int silniaOgon(int n, int akumulator = 1) {
  2.   if (n == 0) {
  3.     return akumulator;
  4.   }
  5.   return silniaOgon(n - 1, akumulator * n);
  6. }

Sztuczka z powyższym kodem polega na tym, że kompilator obsługujący rekurencję ogonową zauważy, że nie ma potrzeby zapisywania ramki na stosie, ponieważ i tak później ma zwrócić wynik kolejnego wywołania. Dzięki temu stos nie rośnie liniowo, a ma stały rozmiar. Większość kompilatorów posiada specjalne mechanizmy, które pozwalają zoptymalizować taką rekurencję.

Ponadto po zakończeniu obliczeń program nie musi zdejmować wszystkich ramek ze stosu tylko od razu zwraca gotowy wynik. Optymalizacja powoduje, że algorytm działa bardzo podobnie do pętli tak jak w poniższym kodzie:

  1. int silniaPetla(int n) {
  2.   int wynik = 1;
  3.   while(n > 0) {
  4.     wynik *= n;
  5.     n--;
  6.   }
  7.   return wynik;
  8. }

Oczywiście pętla oraz rekurencja ogonowa to dwie różne metody pisania programu! W powyższym kodzie akumulatorem jest zmienna wynik, a kolejne wywołania rekurencjne to oklejne iteracji w pętli.

Testowanie funkcji

Po napisaniu funkcji warto przetestować jej działanie np. poniższym kodem:

  1. int main () {
  2.   int n;
  3.   cout << "Podaj liczbe\n n = ";
  4.   cin >> n;
  5.   cout << n << "! = " << silniaOgon(n);
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz funkcję, która wyokna operację na liczbach od 1 do n, gdzie n jest liczbą wprowadzoną przez użytkownika. W wyniku powinna zostać zwrócona suma wszystkich liczb parzystych z zakresu pomniejszona przez sumę liczb nieparzystych. Zastosuj rekurencję ogonową. Przykładowo f(5) = -1 + 2 - 3 + 4 - 5 = -3.