Czy rekurencja jest szybsza niż zapętlanie?

Czy rekurencja jest szybsza od pętli?

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

Wyjaśnienie:

Jeśli budujesz Minimalne operacje ogólnego komputera od zera, " iteracja "jest na pierwszym miejscu jako element konstrukcyjny i jest mniej zasobochłonna niż" rekurencja", ergo jest szybsza.

Budowa pseudo-komputerowej maszyny od podstaw:

Pytanie yourself : What do you need to Oblicz wartość, czyli podążać za algorytmem i osiągać wynik?

Ustalimy hierarchię pojęć, zaczynając od zera i definiując w pierwszej kolejności podstawowe, podstawowe pojęcia, a następnie budując z nimi koncepcje drugiego poziomu i tak dalej.

1. Pierwsza koncepcja: komórki pamięci, przechowywanie, Stan . Aby coś zrobić, potrzebujesz miejsc do przechowywania końcowych i pośrednich wartości wyników. Załóżmy, że mają nieskończoną tablicę" liczb całkowitych " komórek, zwaną pamięcią, M [0..Nieskończona].

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

   A) Ustawianie i przenoszenie komórek pamięci

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

   B) Logika i arytmetyka

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

3. Jest to procesor z procesorem wykonującym. "Agent" to coś, co może wykonywać instrukcje. Agent może być również osobą podążającą za algorytmem na papierze.

4. Kolejność kroków: Sekwencja instrukcje: tzn.: zrób to najpierw, zrób to po itd. Imperatywna Sekwencja instrukcji. Nawet jedna linia wyrażenia są "imperatywnym ciągiem instrukcji". Jeśli masz wyrażenie o określonej "kolejności oceny" to masz kroki. Oznacza to, że nawet pojedyncze wyrażenie złożone ma ukryte "kroki", a także ma ukrytą zmienną lokalną (nazwijmy ją "wynikiem"). np.:

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

   Powyższe wyrażenie implikuje 3 kroki z zmienna implicit "result".

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

   Więc nawet wyrażenia infiksowe, ponieważ masz określoną kolejność oceny, są imperatywną sekwencją instrukcji. Wyrażenie implikuje sekwencję operacji, które mają być wykonane w określonej kolejności, a ponieważ istnieją kroki , istnieje również ukryta zmienna pośrednia "wynik".

5. Instruction Pointer: Jeśli masz sekwencję kroków, masz również implicit " instruction pointer". Wskaźnik instrukcji oznacza następną instrukcję i postępuje po jej przeczytaniu, ale przed jej wykonaniem.

   W tej pseudo-komputerowej maszynie wskaźnik instrukcji jest częścią pamięci. (Uwaga: zwykle wskaźnik będzie "specjalnym rejestrem" w rdzeniu procesora, ale tutaj uprościmy pojęcia i przyjmiemy, że wszystkie dane (rejestry dołączone) są częścią "pamięci")

6. Jump - Once you mając uporządkowaną liczbę kroków i wskaźnik instrukcji , Możesz zastosować instrukcję "store", aby zmienić wartość samego wskaźnika instrukcji. To użycie instrukcji store nazwiemy nową nazwą: Jump. Używamy nowej nazwy, ponieważ łatwiej jest myśleć o niej jako o nowej koncepcji. Zmieniając wskaźnik instrukcji, poinstruujemy agenta, aby "przeszedł do kroku x".

7. Infinite Iteration: By jumping back, Teraz możesz 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. Conditional - warunkowe wykonywanie instrukcji. Za pomocą klauzuli "conditional" można warunkowo wykonać jedną z kilku instrukcji w oparciu o bieżący stan (który można ustawić za pomocą poprzedniej instrukcji).

9. Właściwa iteracja : Teraz z klauzula warunkowa możemy uciec z nieskończonej pętli instrukcji jump back . 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. Nazwa : Nadawanie nazw określonej lokalizacji pamięci przechowującej dane lub trzymającej krok. To tylko" wygoda " mieć. Nie dodajemy żadnych nowych instrukcji, mając możliwość definiowania" nazw " dla lokalizacji pamięci. "Nazewnictwo" nie jest instrukcją dla agencie, to dla nas tylko wygoda. 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 istnieje szereg kroków, które musisz często wykonywać. Możesz zapisać kroki w nazwanej pozycji w pamięci, a następnie przejść do tej pozycji, gdy trzeba je wykonać (wywołać). Na końcu sekwencji musisz zwrócić do punktu wywołania, aby kontynuować egzekucja. Dzięki temu mechanizmowi tworzysz nowe instrukcje (podprogramy), komponując podstawowe instrukcje.

    Wdrożenie: (nie wymaga nowych koncepcji)

    • przechowuj bieżący wskaźnik instrukcji w predefiniowanej pozycji pamięci
    • skok do podprogramu
    • na końcu podprogramu pobierasz wskaźnik instrukcji z predefiniowanego miejsca pamięci, skutecznie przeskakując z powrotem do następującej instrukcji oryginalnego wywołania

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

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

12. Stack : definiujesz przestrzeń pamięci do pracy jako "stos", możesz "push" wartości na stosie, a także" pop " ostatni wartość "wypchnięta". Aby zaimplementować stos, musisz wskaźnik stosu (podobny do wskaźnika instrukcji), który wskazuje na rzeczywistą "głowę" stosu. Kiedy "naciskasz" wartość, wskaźnik stosu maleje i przechowujesz wartość. Kiedy "pop", otrzymasz wartość na faktycznym wskaźniku stosu, a następnie wskaźnik stosu jest zwiększany.

13. Podprogramy Teraz, gdy mamy stos możemy wdrożyć odpowiednie podprogramy zezwalanie na zagnieżdżone wywołania. Implementacja jest podobna, ale zamiast przechowywać wskaźnik instrukcji w predefiniowanej pozycji pamięci, "wciskamy" wartość IP w stosie . Na końcu podprogramu po prostu "pop" wartość ze stosu, skutecznie przeskakując z powrotem do instrukcji po oryginalnym wywołaniu . Implementacja ta, posiadająca "stos" pozwala na wywołanie podprogramu z innego podprogramu. Dzięki tej implementacji możemy stworzyć kilka poziomów abstrakcji przy definiowaniu nowych instrukcji jako podprogramów, używając instrukcji core lub innych podprogramów jako bloków konstrukcyjnych.

14. Rekurencja: co się dzieje, gdy podprogram sam się wywołuje?. Nazywa się to "rekurencją".

    Problem: nadpisanie lokalnych wyników pośrednich podprogram może być przechowywany w pamięci. Ponieważ wywołujesz / ponownie używasz tych samych kroków, Jeśli wyniki pośrednie są przechowywane w predefiniowanych lokalizacje pamięci (zmienne globalne) zostaną nadpisane na zagnieżdżonych wywołaniach.

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

...

Po osiągnięciu rekurencja we stop proszę.

Wniosek:

W architekturze Von Neumanna, wyraźnie "iteracja" jest pojęciem prostszym/podstawowym niż "Rekurencja". Mamy formę "iteracji" na poziomie 7, podczas gdy "rekurencji" jest na poziomie 14 hierarchii pojęć.

iteracja zawsze będzie szybszy w kodzie maszynowym, ponieważ implikuje mniej instrukcji, a więc mniej cykli procesora.

Który z nich jest "lepiej"?

• Powinieneś użyć "iteracji", gdy przetwarzasz proste, sekwencyjne struktury danych, a wszędzie zrobi to" prosta pętla".

• Powinieneś użyć "rekurencji", gdy musisz przetworzyć rekurencyjną strukturę danych (lubię je nazywać "Fraktalnymi strukturami danych"), lub gdy rozwiązanie rekurencyjne jest wyraźnie bardziej "eleganckie".

Porada : użyj najlepszego narzędzia do pracy, ale zrozum wewnętrzne działanie każdego narzędzia w zamów mądrze wybrać.

Na koniec zauważ, że masz wiele możliwości użycia rekurencji. Masz rekurencyjne Struktury Danych wszędzie, patrzysz teraz na jedną: części DOM obsługujące to, co czytasz, to RDS, wyrażenie JSON to RDS, hierarchiczny system plików w Twoim komputerze to RDS, czyli: masz katalog główny, zawierający pliki i katalogi, każdy katalog zawierający pliki i katalogi, każdy z tych katalogów zawierający pliki i katalogi, każdy z tych katalogów zawierający pliki i katalogi. i katalogów...

Rekurencja może być szybsza, gdy alternatywą jest jawne zarządzanie stosem, jak w algorytmach sortowania lub drzewa binarnego, o których wspomniałeś.

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

Więc właściwym podejściem jest najpierw napisać go w najbardziej naturalny sposób, tylko zoptymalizować, jeśli profilowanie pokazuje, że jest krytyczny, a następnie zmierzyć rzekomą poprawę.

Rekurencja ogona jest tak szybka jak zapętlanie. Wiele języków funkcyjnych ma zaimplementowaną rekurencję ogonową.

Zastanów się, co absolutnie należy zrobić dla każdej iteracji i rekurencji.

• iteracja: skok do początku pętli
• rekurencja: skok do początku wywołanej funkcji

Widzisz, że nie ma tu zbyt 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ż rozwiązania iteracyjne. Jest to związane z gromadzeniem i niszczeniem ramek stosu, ale nie jest to dokładnie to. Ogólnie jest to duża różnica w przechowywaniu zmiennej auto dla każdej rekurencji. W algorytmie iteracyjnym z pętlą zmienne są często przechowywane w rejestrach i nawet jeśli się rozleją, będą znajdować się w buforze poziomu 1. W algorytmie rekurencyjnym wszystkie stany pośrednie zmiennej są przechowywane na stosie, co oznacza, że będą wywoływać wiele więcej wycieków do pamięci. Oznacza to, że nawet jeśli wykonuje taką samą ilość operacji, będzie miał wiele dostępu do pamięci w gorącej pętli i co gorsza, te operacje pamięci mają kiepską szybkość ponownego użycia, dzięki czemu pamięci podręczne są mniej skuteczne.

TL; DR algorytmy rekurencyjne mają na ogół gorsze zachowanie pamięci podręcznej niż iteracyjne.

Większość odpowiedzi tutaj są błędne . Prawidłowa odpowiedź to to zależy . Na przykład, oto dwie funkcje C, które przechodzą przez drzewo. Pierwszy 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);
        }
    });
}

I tutaj jest ta sama funkcja zaimplementowana za pomocą 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. Tylko, że p są węzłami i że P_FOR_EACH_CHILD robi chodzenie. W wersji iteracyjnej potrzebujemy jawnego stosu st, na który są wypychane węzły i potem wyskoczył i zmanipulował.

Funkcja rekurencyjna działa znacznie szybciej niż iteracyjna. Powodem jest to, że w tym ostatnim, dla każdego elementu, potrzebna jest {[5] } do funkcji st_push, a następnie Inna do st_pop.

W pierwszym masz tylko rekurencyjny CALL dla każdego węzła.

Dodatkowo, dostęp do zmiennych na callstack jest niewiarygodnie szybki. Oznacza to, że czytasz z pamięci, która prawdopodobnie zawsze będzie w najgłębszej pamięci podręcznej. Jawny stos, na z drugiej strony, musi być wspierana przez malloc: pamięć ed ze sterty, do której dostęp jest znacznie wolniejszy.

Dzięki starannej optymalizacji, takiej jak inlining st_push i 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 wywołania rekurencyjnego.

Ale ta dyskusja jest w większości dyskusyjna, ponieważ rekurencyjne chodzenie po drzewie jest niepoprawne. Jeśli masz wystarczająco duże drzewo, zabraknie Ci przestrzeń callstack, dlatego należy zastosować algorytm iteracyjny.

W każdym realistycznym systemie Nie, tworzenie ramki stosu zawsze będzie droższe niż INC i JMP. Dlatego naprawdę dobre Kompilatory automatycznie przekształcają rekurencję ogonową w wywołanie do tej samej ramki, tzn. bez narzutu, dzięki czemu otrzymujemy bardziej czytelną wersję źródłową i wydajniejszą skompilowaną. naprawdę, naprawdę Dobry kompilator powinien być nawet w stanie przekształcić zwykłą rekurencję w rekurencję ogonową, gdzie jest to możliwe.

Programowanie funkcyjne jest bardziej o " co "zamiast" Jak ".

Implementatorzy języka znajdą sposób na zoptymalizowanie działania kodu pod spodem, jeśli nie spróbujemy uczynić go bardziej zoptymalizowanym niż musi być. Rekurencja może być również zoptymalizowana w językach, które obsługują optymalizację wywołań ogonowych.

Z punktu widzenia programisty najważniejsza jest czytelność i konserwacja, a nie optymalizacja. "Przedwczesny optymalizacja jest źródłem wszelkiego zła".

To jest zgadywanie. Ogólnie rekurencja prawdopodobnie nie pokonuje pętli często lub nigdy w przypadku problemów o przyzwoitej wielkości, jeśli oba używają naprawdę dobrych algorytmów (nie licząc trudności implementacji), może być inaczej, jeśli jest używana z językiem w/ tail call recursion(i algorytmem rekurencyjnym ogonowym i pętlami również jako częścią języka)-który prawdopodobnie miałby bardzo podobne i być może nawet preferuje rekurencję przez jakiś czas.

Ogólnie rzecz biorąc, nie, rekurencja nie będzie szybsza niż pętla w jakimkolwiek realistycznym użyciu, które ma realne implementacje w obu formach. Oczywiście, możesz kodować pętle, które trwają wiecznie, ale są lepsze sposoby implementacji tej samej pętli, które mogą przewyższyć każdą implementację tego samego problemu poprzez rekurencję.

Trafiłeś w sedno, jeśli chodzi o powód; tworzenie i niszczenie ramek stosu jest droższe niż zwykły skok.

Należy jednak pamiętać, że I powiedział "ma realne wdrożenia w obu formach". Dla rzeczy takich jak wiele algorytmów sortowania, wydaje się, że nie ma zbyt realnego sposobu ich implementacji, który nie tworzy efektywnie własnej wersji stosu, ze względu na powstawanie "zadań" potomnych, które są nieodłączną częścią procesu. Tak więc rekurencja może być równie szybka jak próba implementacji algorytmu za pomocą pętli.

Edit: ta odpowiedź zakłada języki niefunkcjonalne, w których większość podstawowych typów danych jest zmienna. Nie stosuje się do języków funkcyjnych.

Według teorii jest to to samo. 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że być kodowany 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;
  }