Czy rekurencja jest zawsze szybsza niż zapętlenie?

Wiem, że rekurencja jest czasem o wiele czystsza niż zapętlanie i nie pytam o to, kiedy powinienem użyć rekurencji po iteracji, wiem, że jest już wiele pytań na ten temat.

Pytam, czy rekurencja jest zawsze szybsza niż pętla? Wydaje mi się, że zawsze będziesz w stanie dopracować pętlę i sprawić, by działała szybciej niż funkcja rekurencyjna, ponieważ pętla nie jest stale ustawiana nowych ramek stosu.

W szczególności szukam, czy rekurencja jest szybsza w aplikacjach, w których rekurencja jest właściwym sposobem obsługi danych, na przykład w niektórych funkcjach sortowania, w drzewach binarnych itp.

Zależy to od używanego języka. Napisałeś „agnostyk językowy”, więc podam kilka przykładów.

W Javie, C i Pythonie rekurencja jest dość droga w porównaniu z iteracją (ogólnie), ponieważ wymaga przydzielenia nowej ramki stosu. W niektórych kompilatorach C można użyć flagi kompilatora, aby wyeliminować ten narzut, który przekształca niektóre typy rekurencji (właściwie niektóre typy wywołań ogonowych) w skoki zamiast wywołań funkcji.

W implementacjach funkcjonalnego języka programowania czasami iteracja może być bardzo droga, a rekurencja może być bardzo tania. W wielu przypadkach rekurencja jest przekształcana w prosty skok, ale zmiana zmiennej pętli (która jest zmienna) czasami wymaga pewnych stosunkowo ciężkich operacji, szczególnie na implementacjach, które obsługują wiele wątków wykonania. Mutacja jest kosztowna w niektórych z tych środowisk ze względu na interakcję między mutatorem a śmieciarzem, jeśli oba mogą być uruchomione w tym samym czasie.

Wiem, że w niektórych implementacjach schematu rekurencja będzie na ogół szybsza niż zapętlenie.

Krótko mówiąc, odpowiedź zależy od kodu i implementacji. Użyj dowolnego stylu. Jeśli używasz funkcjonalnego języka, rekurencja może być szybsza. Jeśli używasz imperatywnego języka, iteracja jest prawdopodobnie szybsza. W niektórych środowiskach obie metody spowodują wygenerowanie tego samego zestawu (włóż go do rury i wypal go).

Dodatek: W niektórych środowiskach najlepszą alternatywą nie jest rekurencja ani iteracja, ale funkcje wyższego rzędu. Należą do nich „mapa”, „filtr” i „zmniejsz” (co jest również nazywane „fold”). Są to nie tylko preferowane style, nie tylko często są one czystsze, ale w niektórych środowiskach funkcje te są pierwszymi (lub jedynymi), które korzystają z automatycznej równoległości - dzięki czemu mogą być znacznie szybsze niż iteracja lub rekurencja. Data Parallel Haskell jest przykładem takiego środowiska.

Wyrażenia listowe to kolejna alternatywa, ale zwykle są to tylko cukier syntaktyczny do iteracji, rekurencji lub funkcji wyższego rzędu.

czy rekurencja jest zawsze szybsza niż pętla?

Nie, iteracja zawsze będzie szybsza niż rekurencja. (w architekturze von Neumanna)

Wyjaśnienie:

Jeśli zbudujesz od podstaw minimalną liczbę operacji na komputerze ogólnym, „Iteracja” jest najważniejsza jako element konstrukcyjny i wymaga mniej zasobów niż „rekurencja”, więc ergo jest szybsze.

Budowanie pseudokomputera od zera:

Zadaj sobie pytanie : czego potrzebujesz, aby obliczyć wartość, tj. Postępować zgodnie z algorytmem i osiągnąć wynik?

Ustanowimy hierarchię pojęć, zaczynając od zera i definiując przede wszystkim podstawowe, podstawowe pojęcia, a następnie budujemy z nimi pojęcia drugiego poziomu i tak dalej.

1. Pierwsza koncepcja: komórki pamięci, pamięć, stan . Aby coś zrobić, potrzebujesz miejsca do przechowywania końcowych i pośrednich wartości wyników. Załóżmy, że mamy nieskończoną tablicę komórek „całkowitych”, zwanych Memory , M [0..Infinite].

2. Instrukcje: zrób coś - przekształć komórkę, zmień jej wartość. zmienić stan . Każda ciekawa instrukcja wykonuje transformację. Podstawowe instrukcje to:

   a) Ustaw i przenieś komórki pamięci

   • zapisz wartość w pamięci, np .: zapisz 5 m [4]
   • skopiuj wartość do innej pozycji: np .: zapisz m [4] m [8]

   b) Logika i arytmetyka

   • i, lub xor, nie
   • dodaj, sub, mul, div. np. dodaj m [7] m [8]

3. Agent wykonujący : rdzeń nowoczesnego procesora. „Agent” to coś, co może wykonywać instrukcje. Agenta może być także osoba następujący algorytm na papierze.

4. Kolejność kroków: sekwencja instrukcji : tj. Zrób to najpierw, zrób to później itp. Konieczna sekwencja instrukcji. Nawet wyrażenia jednej linii są „bezwzględną sekwencją instrukcji”. Jeśli masz wyrażenie z określoną „kolejnością oceny”, masz kroki . Oznacza to, że nawet jedno złożone wyrażenie ma niejawne „kroki”, a także niejawną zmienną lokalną (nazwijmy to „wynikiem”). na przykład:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   Powyższe wyrażenie oznacza 3 kroki z niejawną zmienną „wynik”.

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   Tak więc nawet wyrażenia niepoprawne, ponieważ masz określoną kolejność oceny, są konieczną sekwencją instrukcji . Wyrażenie implikuje sekwencję operacji, które należy wykonać w określonej kolejności, a ponieważ istnieją kroki , istnieje również domniemana zmienna pośrednia „wynik”.

5. Wskaźnik instrukcji : Jeśli masz sekwencję kroków, masz również domyślny „wskaźnik instrukcji”. Wskaźnik instrukcji oznacza następną instrukcję i przesuwa się po jej odczytaniu, ale przed wykonaniem instrukcji.

   W tej pseudo-maszynie obliczeniowej wskaźnik instrukcji jest częścią pamięci . (Uwaga: normalnie wskaźnik instrukcji będzie „specjalnym rejestrem” w rdzeniu procesora, ale tutaj uprościmy koncepcje i założymy, że wszystkie dane (łącznie z rejestrami) są częścią „pamięci”)

6. Skok - po uzyskaniu uporządkowanej liczby kroków i wskaźnika instrukcji można zastosować instrukcję „ zapisz ”, aby zmienić wartość samego wskaźnika instrukcji. Będziemy nazywać to konkretne użycie instrukcji sklepu nową nazwą: Jump . Używamy nowej nazwy, ponieważ łatwiej jest myśleć o niej jako o nowej koncepcji. Zmieniając wskaźnik instrukcji, instruujemy agenta, aby „poszedł do kroku x”.

7. Nieskończona iteracja : Odskakując , możesz teraz sprawić, że agent „powtórzy” określoną liczbę kroków. W tym momencie mamy nieskończoną iterację.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. Warunkowe - warunkowe wykonanie instrukcji. Dzięki klauzuli „warunkowej” możesz warunkowo wykonać jedną z kilku instrukcji na podstawie bieżącego stanu (który można ustawić za pomocą poprzedniej instrukcji).

9. Właściwa iteracja : Teraz dzięki klauzuli warunkowej możemy uciec od nieskończonej pętli instrukcji cofania . Mamy teraz pętlę warunkową, a następnie właściwą iterację

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous 
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. Nazewnictwo : nadawanie nazw konkretnej lokalizacji pamięci przechowującej dane lub trzymającej stopień . To tylko „wygoda”. Nie dodajemy żadnych nowych instrukcji, ponieważ możemy zdefiniować „nazwy” dla lokalizacji pamięci. „Nazewnictwo” nie jest instrukcją dla agenta, jest dla nas jedynie wygodą. Nazewnictwo sprawia, że ​​kod (w tym momencie) jest łatwiejszy do odczytania i łatwiejszy do zmiany.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. Podprogram jednopoziomowy : Załóżmy, że musisz wykonać szereg czynności często. Możesz zapisać kroki w nazwanej pozycji w pamięci, a następnie przeskoczyć do tej pozycji, kiedy trzeba je wykonać (połączenie). Na końcu sekwencji musisz wrócić do punktu wywołania, aby kontynuować wykonywanie. Dzięki temu mechanizmowi tworzysz nowe instrukcje (podprogramy), tworząc podstawowe instrukcje.

    Wdrożenie: (nie są wymagane nowe koncepcje)

    • Przechowuj bieżący wskaźnik instrukcji we wstępnie zdefiniowanej pozycji w pamięci
    • przejść do podprogramu
    • na końcu podprogramu pobiera się wskaźnik instrukcji ze wstępnie zdefiniowanego miejsca w pamięci, skutecznie skacząc z powrotem do następującej instrukcji pierwotnego wywołania

    Problem z implementacją jednopoziomową : Nie można wywołać innego podprogramu z podprogramu. Jeśli to zrobisz, nadpiszesz adres zwrotny (zmienna globalna), więc nie możesz zagnieżdżać połączeń.

    Aby mieć lepszą implementację podprogramów: Potrzebujesz stosu

12. Stos : definiujesz przestrzeń pamięci jako „stos”, możesz „wypychać” wartości na stosie, a także „pop” ostatnią „wypchniętą” wartość. Aby wdrożyć stos, potrzebujesz wskaźnika stosu (podobnego do wskaźnika instrukcji), który wskazuje na rzeczywistą „głowę” stosu. Kiedy „wypychasz” wartość, wskaźnik stosu zmniejsza się i zapisujesz wartość. Kiedy „wyskakujesz”, otrzymujesz wartość przy rzeczywistym wskaźniku stosu, a następnie wskaźnik stosu jest zwiększany.

13. Podprogramy Teraz, gdy mamy stos , możemy zaimplementować odpowiednie podprogramy umożliwiające zagnieżdżanie wywołań . Implementacja jest podobna, ale zamiast przechowywać wskaźnik instrukcji we wstępnie zdefiniowanej pozycji pamięci, „wypychamy” wartość adresu IP na stos . Na końcu podprogramu po prostu „wyskakujemy” wartość ze stosu, skutecznie skacząc z powrotem do instrukcji po pierwotnym wywołaniu . Ta implementacja, posiadająca „stos”, umożliwia wywołanie podprogramu z innego podprogramu. Dzięki tej implementacji możemy stworzyć kilka poziomów abstrakcji podczas definiowania nowych instrukcji jako podprogramów, wykorzystując podstawowe instrukcje lub inne podprogramy jako bloki konstrukcyjne.

14. Rekurencja : Co się dzieje, gdy podprogram wywołuje się ?. Nazywa się to „rekurencją”.

    Problem: Nadpisanie lokalnych wyników pośrednich, które podprogram może przechowywać w pamięci. Ponieważ wywołujesz / ponownie używasz tych samych kroków, jeśli wynik pośredni jest przechowywany w predefiniowanych lokalizacjach pamięci (zmienne globalne), zostaną one zastąpione w zagnieżdżonych wywołaniach.

    Rozwiązanie: Aby umożliwić rekurencję, podprogramy powinny przechowywać lokalne wyniki pośrednie na stosie , dlatego przy każdym wywołaniu rekurencyjnym (bezpośrednim lub pośrednim) wyniki pośrednie są przechowywane w różnych lokalizacjach pamięci.

...

po osiągnięciu rekurencji zatrzymujemy się tutaj.

Wniosek:

W architekturze von Neumanna wyraźnie „Iteracja” jest prostszą / podstawową koncepcją niż „Rekurencja” . Mamy formę „Iteracji” na poziomie 7, podczas gdy „Rekurencja” znajduje się na poziomie 14 hierarchii pojęć.

Iteracja zawsze będzie szybsza w kodzie maszynowym, ponieważ implikuje mniej instrukcji, a zatem mniej cykli procesora.

Który jest lepszy"?

• Powinieneś używać „iteracji”, gdy przetwarzasz proste, sekwencyjne struktury danych i wszędzie tam, gdzie zrobi to „prosta pętla”.

• Powinieneś użyć „rekurencji”, gdy potrzebujesz przetworzyć rekurencyjną strukturę danych (lubię je nazywać „Fractal Data Structures”), lub gdy rekurencyjne rozwiązanie jest wyraźnie bardziej „eleganckie”.

Rada : użyj najlepszego narzędzia do pracy, ale zrozum wewnętrzny mechanizm działania każdego narzędzia, aby mądrze wybrać.

Na koniec zauważ, że masz wiele możliwości korzystania z rekurencji. Wszędzie masz Rekurencyjne Struktury Danych , na które teraz patrzysz: części DOM obsługujące to, co czytasz, to RDS, wyrażenie JSON to RDS, hierarchiczny system plików na twoim komputerze to RDS, tzn .: masz katalog główny zawierający pliki i katalogi, każdy katalog zawierający pliki i katalogi, każdy katalog zawierający pliki i katalogi ...

Rekurencja może być szybsza tam, gdzie alternatywą jest jawne zarządzanie stosem, na przykład w algorytmach sortowania lub drzewa binarnego, o których wspominasz.

Miałem przypadek, w którym przepisanie algorytmu rekurencyjnego w Javie spowolniło go.

Tak więc właściwym podejściem jest najpierw napisanie go w najbardziej naturalny sposób, optymalizacja tylko wtedy, gdy profilowanie pokazuje, że jest to krytyczne, a następnie zmierzenie domniemanej poprawy.

Rekurencja ogona jest tak szybka jak zapętlenie. Wiele języków funkcjonalnych ma zaimplementowaną rekurencję ogona.

Zastanów się, co absolutnie trzeba zrobić dla każdego, iteracji i rekurencji.

• iteracja: skok do początku pętli
• rekurencja: skok na początek wywoływanej funkcji

Widzisz, że nie ma tu wiele miejsca na różnice.

(Zakładam, że rekurencja jest wywołaniem ogonowym, a kompilator jest świadomy tej optymalizacji).

Większość odpowiedzi tutaj zapomina oczywistego winowajcę, dlaczego rekurencja jest często wolniejsza niż iteracyjne rozwiązania. Jest to powiązane z narastaniem i rozbijaniem ramek stosu, ale nie jest dokładnie takie. Zasadniczo jest to duża różnica w przechowywaniu zmiennej automatycznej dla każdej rekurencji. W iteracyjnym algorytmie z pętlą zmienne są często przechowywane w rejestrach, a nawet jeśli się rozleją, będą znajdować się w pamięci podręcznej poziomu 1. W algorytmie rekurencyjnym wszystkie stany pośrednie zmiennej są przechowywane na stosie, co oznacza, że ​​spowodują one o wiele więcej wycieków do pamięci. Oznacza to, że nawet jeśli wykona taką samą liczbę operacji, będzie miał duży dostęp do pamięci w gorącej pętli, a co gorsza, te operacje pamięci mają kiepską częstotliwość ponownego użycia, co powoduje, że pamięci podręczne są mniej skuteczne.

Algorytmy rekurencyjne TL; DR mają ogólnie gorsze zachowanie w pamięci podręcznej niż iteracyjne.

Większość odpowiedzi tutaj jest błędna . Właściwa odpowiedź to zależy . Na przykład tutaj są dwie funkcje C, które przechodzą przez drzewo. Najpierw rekurencyjny:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

A oto ta sama funkcja zaimplementowana przy użyciu iteracji:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

Nie jest ważne, aby zrozumieć szczegóły kodu. Po prostu to psą węzły i P_FOR_EACH_CHILDto idzie. W wersji iteracyjnej potrzebujemy jawnego stosu, stna który węzły są wpychane, a następnie otwierane i manipulowane.

Funkcja rekurencyjna działa znacznie szybciej niż iteracyjna. Powodem jest to, że w tym drugim przypadku dla każdego elementu potrzebna jest CALLfunkcja st_pusha, a następnie inna do st_pop.

W pierwszym przypadku rekursywny jest tylko CALLdla każdego węzła.

Co więcej, dostęp do zmiennych w callstacku jest niesamowicie szybki. Oznacza to, że czytasz z pamięci, która prawdopodobnie zawsze znajduje się w wewnętrznej pamięci podręcznej. Z drugiej strony jawny stos musi być wspierany przez malloc: ed pamięć ze sterty, do której dostęp jest znacznie wolniejszy.

Dzięki starannej optymalizacji, takiej jak wstawianie st_pushi st_pop, mogę osiągnąć mniej więcej równość z podejściem rekurencyjnym. Ale przynajmniej na moim komputerze koszt dostępu do pamięci sterty jest większy niż koszt połączenia rekurencyjnego.

Ale ta dyskusja jest w większości dyskusyjna, ponieważ rekurencyjne chodzenie po drzewach jest nieprawidłowe . Jeśli masz wystarczająco duże drzewo, zabraknie miejsca na stos wywołań, dlatego należy zastosować algorytm iteracyjny.

Zasadniczo nie, rekurencja nie będzie szybsza niż pętla w jakimkolwiek realistycznym zastosowaniu, które ma wykonalne implementacje w obu formach. Mam na myśli, że możesz kodować pętle, które trwają wiecznie, ale byłyby lepsze sposoby implementacji tej samej pętli, która mogłaby przewyższyć każdą implementację tego samego problemu poprzez rekurencję.

Uderzyłeś się w głowę o powód; tworzenie i niszczenie ram stosów jest droższe niż zwykły skok.

Należy jednak zauważyć, że powiedziałem „ma realne wdrożenia w obu formach”. W przypadku wielu algorytmów sortowania, nie jest to bardzo opłacalny sposób ich implementacji, który nie tworzy efektywnie własnej wersji stosu, ze względu na pojawianie się „zadań” potomnych, które są nieodłącznie częścią tego procesu. Zatem rekurencja może być tak samo szybka, jak próba implementacji algorytmu za pomocą pętli.

Edycja: Ta odpowiedź zakłada, że ​​języki niefunkcjonalne, w których większość podstawowych typów danych jest zmienna. Nie dotyczy języków funkcjonalnych.

W każdym realistycznym systemie tworzenie ramki stosu zawsze będzie droższe niż INC i JMP. Dlatego naprawdę dobre kompilatory automatycznie przekształcają rekursję ogona w wywołanie do tej samej ramki, tj. Bez narzutu, dzięki czemu otrzymujesz bardziej czytelną wersję źródłową i bardziej wydajną wersję skompilowaną. Naprawdę dobry kompilator powinien nawet być w stanie przekształcić normalne rekursji w rekursji ogonowej, gdzie jest to możliwe.

Programowanie funkcjonalne polega raczej na „ czym ” niż na „ jak ”.

Implementatory języka znajdą sposób na zoptymalizowanie działania kodu pod spodem, jeśli nie spróbujemy go bardziej zoptymalizować, niż trzeba. Rekurencję można również zoptymalizować w językach, które obsługują optymalizację wezwania ogona.

Z punktu widzenia programisty bardziej liczy się czytelność i łatwość konserwacji niż optymalizacja. Znów „przedwczesna optymalizacja jest źródłem wszelkiego zła”.

To przypuszczenie. Zasadniczo rekurencja prawdopodobnie nie pokonuje często lub nigdy nie pętli problemów o przyzwoitym rozmiarze, jeśli oba wykorzystują naprawdę dobre algorytmy (nie licząc trudności z implementacją), może być inna, jeśli jest używana z rekurencją języka w / wywołaniem ogona (i algorytmem rekurencji ogona oraz z pętlami również jako częścią języka) - który prawdopodobnie miałby bardzo podobny, a być może nawet wolałby rekurencję.

Według teorii są to te same rzeczy. Rekurencja i pętla o tej samej złożoności O () będą działać z tą samą prędkością teoretyczną, ale oczywiście rzeczywista prędkość zależy od języka, kompilatora i procesora. Przykład z potęgą liczby można kodować w sposób iteracyjny za pomocą O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }