Ogólne pytania dotyczące rekurencji

Question

Jak rozumiem, dobre rekurencyjne rozwiązania mogą sprawić, że skomplikowane problemy staną się łatwiejsze. Mogą być bardziej wydajne pod względem czasu lub przestrzeni.

Moje pytanie brzmi: nie jest za darmo, a stos wywołań będzie bardzo głęboki. Spowoduje to dużo pamięci. Czy mam rację?

Answer 1

Trudno precyzyjnie określić kompromisy związane z rekurencją.

Na poziomie matematycznie abstrakcyjnym rekursja daje potężne ramy do opisu jawnego zachowania funkcji. Na przykład, możemy matematycznie definiować silni jak

x! = 1    if x == 0 
x! = x * (x - 1)! else 

Albo możemy określić bardziej złożoną funkcję rekurencyjnie, jak w jaki sposób możemy obliczyć „N wybrać K”:

C(n, k) = 1        if k == 0 
C(n, k) = 0        if k < 0 or if n > k 
C(n, k) = C(n - 1, k) + C(n - 1, k - 1) else 

Przy użyciu rekursji jako techniki implementacji, nie ma gwarancji, że skończy się używanie większej ilości pamięci lub tworzenie kodu, który działa bardziej wydajnie. Często rekurencja wykorzystuje więcej miejsca ze względu na pamięć wymaganą do przechowywania ramek stosu, ale w niektórych językach nie stanowi to problemu, ponieważ kompilator może próbować zoptymalizować wywołania funkcji (patrz na przykład eliminacja wywołań końcowych). W innych przypadkach rekurencja może zużyć ogromne zasoby do punktu, w którym kod rekursywny może przestać kończyć się prostymi problemami.

Co do problemów związanych z wydajnością, często kod rekurencyjny jest znacznie mniej wydajny niż kod iteracyjny. Wywołania funkcji są drogie, a naiwne tłumaczenie rekursji na kod prowadzi do niepotrzebnego powielania pracy. Na przykład, naiwna implementacja Fibonacciego

int Fibonacci(int n) { 
    if (n <= 1) return n; 
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
} 

Czy horrendalnie nieefektywne i jest tak powolny, że nigdy nie jest stosowany w praktyce. Chociaż kod jest czystszy, nieefektywność zżera wszelkie potencjalne korzyści rekurencji.

W innych przypadkach rekursja może być niesamowitą oszczędnością czasu.Jako przykład mergesort jest bardzo szybki algorytm sortowania zdefiniowane przez piękną rekursji:

Mergesort(array, low, high) { 
    if (low >= high - 1) return; 
    Mergesort(array, low, low + (high - low)/2); 
    Mergesort(array, low + (high - low)/2, high); 
    Merge(array, low, low + (high - low)/2, high); 
} 

Kod ten jest bardzo szybki i odpowiedni kod iteracyjny będzie prawdopodobnie wolniejsze, trudniejsze do odczytania, i trudniejsze do zrozumienia.

Krótko mówiąc, rekursja nie jest ani magicznym lekarstwem, ani siłą, której należy unikać. Pomaga oświetlić strukturę wielu problemów, które w przeciwnym razie mogą wydawać się trudne lub prawie niemożliwe. Chociaż często prowadzi to do wyraźniejszego kodu, często dzieje się tak kosztem czasu i pamięci (choć niekoniecznie jest to automatycznie mniej wydajne, w wielu przypadkach może być wydajniejsze). Zdecydowanie warto studiować, aby poprawić ogólne myślenie algorytmiczne i umiejętności rozwiązywania problemów, nawet jeśli nigdy nie napiszesz innej funkcji rekursywnej w swoim życiu.

Mam nadzieję, że to pomoże!

Answer 2

Cons: 
It is hard (especially for inexperienced programmers) to think recursively 
There also exists the problem of stack overflow when using some forms of recursion (head 
recursion). 
It is usually less efficient because of having to push and pop recursions on and off the 
run-time stack, so it can be slower to run than simple iteration. 

Ale dlaczego zawracamy sobie głowę wykorzystaniem rekursji?

Pros: 
It is easier to code a recursive solution once one is able to identify that solution. The 
recursive code is usually smaller, more concise, more elegant, and possibly even easier to 
understand, though that depends on one’s thinking style☺ 
There are some problems that are very difficult to solve without recursion. Those problems 
that require backtracking such as searching a maze for a path to an exit or tree based 
operations are best solved recursively. 

Answer 3

Praktycznie stos wywołań nie będzie zbyt głęboki. Weźmy na przykład algorytm dziel i podbijaj jak quicksort, który dzieli problem na dwie połowy. Za pomocą stosu połączeń o głębokości 32 można sortować elementy 4G, które prawdopodobnie nie zmieszczą się nawet w pamięci przeciętnego komputera. Zużycie pamięci nie stanowi problemu, jest to stos i jest darmowy, o ile nie zabraknie go (a na 32 poziomach masz dużo danych do przechowywania na każdym poziomie).

Możesz przepisać praktycznie wszystkie procesy rekursywne na iteracyjne, jeśli utrzymasz stan na stertę w strukturze stosu, ale to tylko komplikuje kod. Głównym scenariuszem, w którym można uzyskać realne korzyści z przepisywania, jest kod rekurencyjny tail, który nie musi utrzymywać stanu dla każdego wywołania rekursywnego. Zauważ, że dla niektórych języków (najbardziej funkcjonalne języki programowania i C/C++, może również Java) dobry kompilator może to dla ciebie zrobić.

Answer 4

To zależy. Problemy, dla których rekursja jest najbardziej odpowiednia, będą odporne na ten problem. Typowym przykładem może być Mergesort, w którym do sortowania listy N elementów będzie dotyczyło ramek stosu log2 (N). Jeśli więc twój limit ramek wynosi 200, a do czasu, gdy zadzwonisz do Mergesort, użyłeś 50, to jest wystarczająco dobre, by sortować około 2 150 elementów bez przepełnienia stosu. Ponadto, Mergesort nie tworzy dużej ilości pamięci dla każdej ramki stosu, więc całkowite wykorzystanie pamięci dla Mergesort nie powinno nigdy być znacznie większe niż podwojona wielkość oryginalnej listy.

Ponadto, niektóre języki (Schemat jest dobrym przykładem) użyj tail-call elimination, aby kod mógł być elegancko zapisany przy użyciu rekurencji, ale następnie zoptymalizowany lub skompilowany w pętlę iteracyjną. Jest to jeden ze sposobów, w jaki LISP, będąc językiem funkcjonalnym, wciąż jest w stanie konkurować z C i C++ pod względem szybkości realizacji.

Istnieje inna technika o nazwie Trampolining, która może być używana do wykonywania pozornie rekursywnych operacji bez generowania stosu wywołań w trybie deep. Ale jeśli nie zostanie ona wbudowana w bibliotekę, a nawet w konstrukt na poziomie języka, technika ta ma mniej wyraźną przewagę w wydajności (moim zdaniem).

Tak więc, chociaż w wielu sytuacjach trudno dyskutować z dobrą starą pętlą for x in xrange(10), rekursja ma swoje miejsce.

Answer 5

Jest to kosztowne, jeśli rekurencja nie jest rekursywna, a język nie obsługuje rekurencji ogona. Zobacz następujący artykuł na Wikipedii połączeń ogona do dyskusji na temat:

http://en.wikipedia.org/wiki/Tail_call

W przeciwnym razie, może to uczynić kod znacznie łatwiejsze do odczytania i łatwiejsze do testowania.

Answer 6

To zależy od problemu.

Jeśli problem wymaga rekurencji, podobnie jak pierwszy spacer po drzewie, jedynym sposobem uniknięcia rekursji jest zasymulowanie go poprzez napisanie własnego stosu. To niczego nie uratuje.

Jeśli problem nie wymaga rekursji, jak zwykle funkcja silnia lub funkcja fibonacci, jaki jest sens? Nic nie zyskujesz, używając go.

Jest to dość mała klasa problemów, w których można nawet mieć rozsądny wybór.