Rekurencja ogonowa i jej optymalizacja

Rekurencja to Rekurencja. Tutaj nawet google się nie myli.

Rekurencja

Czyli inaczej funkcja wywołująca samą siebie. Robi tak aż do osiągnięcia wartości granicznych – na przykład przy ciągu Fibonacciego, aż do osiągnięcia 1 albo 0. Rekurencja do prostych rzeczy nie należy i wiem, że sprawia ona problemy. Zresztą czytając kod różnych programistów widziałem, że raczej robili wszystko by tylko nie wejść w rekurencje.

Zanim więc przejdziemy do bardziej zaawansowanych tematów, dwa przykłady rekurencji:

public static long factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }

    return n * factorial(n - 1);
}

public static long fib(int n)
{
    // could be n == 0 || n == 1 return n;
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return n;
    }

    return fib(n - 2) + fib(n - 1);
}

Jak widzicie nie jest to jakieś super skomplikowane. Trzeba tylko przestawić swój tok myślowy. Może się wam wydawać, że taki błahe przykłady nic nie wniosą do waszej codziennej pracy. Nic bardziej mylnego. W typowej aplikacji biznesowej rekurencja występuje minimum raz – albo to jest moje własne doświadczenie. Czy to stworzenie menu do aplikacji, czy obliczenie czegoś. Szczerze, nauczcie się jej. Przyda się wam na pewno.

Warto też wiedzieć, że każde wywołanie funkcji powoduje dodanie jej do stosu wywołań (call stack, to właśnie daje wam StackTrace w C# przy wyjątkach oraz okno Call Stack w trakcie debuggowania) funkcji – dokładnie trzymana jest informacja do którego miejsca kod ma przeskoczyć jak skończy wywoływać funkcję. Jeżeli teraz mamy jakiś duży zbiór danych, czy też błędnie napisane warunki wyjścia, przy rekurencji łatwo jest ten stos zatkać. A jak się stos zatyka to dostajemy śliczny StackOverflowException. Dla przykładu, metoda bez warunku wyjścia:

public static string stack_overflow_ex(int n)
{
    return stack_overflow_ex(n);
}

Wygeneruje:

Przy rekurencji jest to problem na który możemy dość często natrafić – albo mamy złe warunki wyjścia albo po prostu nasz zbiór danych jest tak duży, że nie starcza nam miejsca na dodanie informacji do call stack.

Tail recursion/Rekurencja ogonowa

To skoro wiemy co to jest rekurencja i co powoduje wywołanie funkcji, pora dowiedzieć się co to jest tail recursion a dokładnie tail call, który w szczególnym przypadku zwie się rekurencją ogonową. Tail call to nic innego jak wywołanie funkcji na końcu aktualnej funkcji:

private int method()
{
	// …
	return tail_call();
}

private int tail_call()
{
	return 1;
}

Tail recursion za to, jest to wywołanie tej samej funkcji w której jesteśmy na końcu tej funkcji:

private int tail_recurssion(int someParam)
{
	// …
	return tail_recurssion(someParam + 1);
}

Dla przykładu Fibbonaci z początku możemy zamienić na wywołanie jedno funkcyjne robiąc z tego tail recursion:

public static long fib(int n, long a, long b)
{
    // short: return n == 0 ? b : fib(n - 1, a + b, a);
    if (n == 0)
    {
        return b;
    }

    return fib(n - 1, a + b, a);
}

Czym to się różni? Tym, że jest tylko jedna metoda na końcu wywoływana – to jest dość ważne.

Teraz, mając tail recursion może zostać zastosowana optymalizacja kodu polegająca na tym, że NIE JEST DODAWANY kolejny stack frame do call stack. By to zademonstrować muszę posłużyć się F#. C# nie posiada optymalizacji tail call. A więc stwórzmy sobie dwie funkcje w F#:

exception BrkError of string

let rec fib_normal n =
    match n with
    | 0 -> raise(BrkError("see_callstack")) // or 0 and brk point
    | 1 -> 1
    | n -> fib_normal(n-2) + fib_normal(n-1)

let rec fib_tail (n, a, b) =
    match n with
    | 0 -> raise(BrkError("see_callstack")) // or b and brk point
    | n -> fib_tail(n-1, a+b, a) 

Wyrzucam wyjątek bo jest tak łatwiej wam to skopiować i wkleić. W razie co, w komentarzu macie podane co można zamiast wywołania wyjątku zrobić. Te dwa kody generują następujące Call Stack:

Jak widzicie, nie ma alokacji call stack dla wersji z fib_tail. A to znaczy, że nie osiągniemy stack overflow. Wszystko jest stałe, proste. To znaczy, że ze złożoności liniowej O(n) weszliśmy na stałą O(1) (Update 2016-10-26: tak jak Patryk zaznaczył w komentarzu, chodzi o złożoność pamięciową).

Podsumowanie

Wiedza co to jest rekurencja, tail call, rekurencja ogonowa i na czym polega optymalizacja tego jest dość podstawową wiedzą w programowaniu i warto ją posiadać – wiedza już o tym jakiego typu algorytmy są wykorzysytwane do wykrywania tail call to już inna broszka. Chociażby tylko po to by zrozumieć dlaczego coś nam się wysypuje nie wspominając już o językach funkcyjnych, w których bez rekurencji ani rusz. Dodatkowo, rekurencja dość często występuje w programowaniu – możemy tego nie zauważyć gdyż czasami się jej boimy, a nie powinniśmy. A jak się czegoś boimy to szukamy alternatywnej drogi wykonania tego. Następnym więc razem jak będziecie pisali pętle while zastanówcie się czy nie da się tego zrobić za pomocą rekurencji. Po prostu pomyślcie, zastanówcie się, napiszcie ten kod i zobaczcie którą wersję wolicie. Tę zachowajcie a drugą wywalcie z kodu :)