Czy jest jakiś spadek wydajności, jeśli użyjemy pętli zamiast rekurencji lub odwrotnie w algorytmach, w których oba mogą służyć temu samemu celowi? Np .: Sprawdź, czy podany ciąg jest palindromem. Widziałem wielu programistów wykorzystujących rekurencję jako sposób na popisanie się, kiedy prosty algorytm iteracji może zmieścić się w rachunku. Czy kompilator odgrywa istotną rolę w podejmowaniu decyzji, których użyć?

Możliwe, że rekurencja będzie droższa, w zależności od tego, czy funkcja rekurencyjna jest rekurencyjna (ostatnia linia to wywołanie rekurencyjne). Rekurencja ogona powinna zostać rozpoznana przez kompilator i zoptymalizowana pod kątem iteracyjnego odpowiednika (przy jednoczesnym zachowaniu zwięzłej, przejrzystej implementacji zawartej w kodzie).

Napiszę algorytm w sposób, który jest najbardziej sensowny i najbardziej zrozumiały dla biednego frajera (czy to ty, czy ktoś inny), który musi zachować kod w ciągu kilku miesięcy lub lat. Jeśli wystąpią problemy z wydajnością, profiluj swój kod, a następnie i tylko wtedy spróbuj zoptymalizować, przechodząc do iteracyjnej implementacji. Możesz zajrzeć do zapamiętywania i programowania dynamicznego .

Pętle mogą osiągnąć wzrost wydajności dla twojego programu. Rekurencja może osiągnąć wzrost wydajności dla programisty. Wybierz, co jest ważniejsze w twojej sytuacji!

Porównanie rekurencji z iteracją jest jak porównanie śrubokręta krzyżakowego z płaskim śrubokrętem. W przeważającej części, którą mógłby usunąć śrubę Phillips głowy z płaskim łbem, ale byłoby to po prostu łatwiej, jeśli użył śrubokręta przeznaczony do tego prawa ślimaka?

Niektóre algorytmy nadają się do rekurencji ze względu na sposób ich zaprojektowania (sekwencje Fibonacciego, przemierzanie struktury podobnej do drzewa itp.). Rekurencja sprawia, że ​​algorytm jest bardziej zwięzły i łatwiejszy do zrozumienia (dlatego można go udostępniać i używać ponownie).

Ponadto niektóre algorytmy rekurencyjne używają „Lazy Evaluation”, co czyni je bardziej wydajnymi niż ich iteracyjni bracia. Oznacza to, że wykonują one drogie obliczenia tylko wtedy, gdy są potrzebne, a nie za każdym razem, gdy pętla działa.

To powinno wystarczyć, aby zacząć. Wykopię też dla ciebie kilka artykułów i przykładów.

Link 1: Haskel vs PHP (Recursion vs Iteration)

Oto przykład, w którym programista musiał przetworzyć duży zestaw danych za pomocą PHP. Pokazuje, jak łatwo byłoby poradzić sobie w Haskel za pomocą rekurencji, ale ponieważ PHP nie miał łatwego sposobu na wykonanie tej samej metody, musiał użyć iteracji, aby uzyskać wynik.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Link 2: Mastering Recursion

Większość złej reputacji rekurencji wynika z wysokich kosztów i nieefektywności w imperatywnych językach. Autor tego artykułu mówi o tym, jak zoptymalizować algorytmy rekurencyjne, aby były szybsze i bardziej wydajne. Zastanawia się także, jak przekształcić tradycyjną pętlę w funkcję rekurencyjną i jakie korzyści przynosi stosowanie rekurencji na końcu. Jego końcowe słowa naprawdę podsumowały niektóre z moich kluczowych punktów, które myślę:

„programowanie rekurencyjne daje programiście lepszy sposób organizowania kodu w sposób, który jest łatwy w utrzymaniu i logicznie spójny”.

https://developer.ibm.com/articles/l-recurs/

Link 3: Czy rekurencja jest zawsze szybsza niż zapętlenie? (Odpowiedź)

Oto link do odpowiedzi na pytanie typu stackoverflow podobne do twojego. Autor zwraca uwagę, że wiele testów porównawczych związanych z rekurencją lub zapętleniem jest bardzo specyficznych dla danego języka. Języki imperatywne są zwykle szybsze przy użyciu pętli i wolniejsze z rekurencją i odwrotnie dla języków funkcjonalnych. Wydaje mi się, że głównym punktem tego linku jest to, że bardzo trudno jest odpowiedzieć na pytanie w języku agnostycznym / ślepym na sytuacje.

Czy rekurencja jest zawsze szybsza niż zapętlenie?

Rekurencja jest droższa w pamięci, ponieważ każde wywołanie rekurencyjne wymaga na ogół wypchnięcia adresu pamięci na stos - aby później program mógł wrócić do tego punktu.

Mimo to istnieje wiele przypadków, w których rekurencja jest o wiele bardziej naturalna i czytelna niż pętle - na przykład podczas pracy z drzewami. W takich przypadkach zalecam trzymanie się rekursji.

Zazwyczaj można oczekiwać, że kara za wyniki będzie leżeć w innym kierunku. Wywołania rekurencyjne mogą prowadzić do budowy dodatkowych ramek stosu; kara za to jest różna. Ponadto w niektórych językach, takich jak Python (bardziej poprawnie, w niektórych implementacjach niektórych języków ...) można dość łatwo napotkać limity stosu dla zadań, które można określić rekurencyjnie, takich jak znalezienie maksymalnej wartości w strukturze danych drzewa. W takich przypadkach naprawdę chcesz trzymać się pętli.

Pisanie dobrych funkcji rekurencyjnych może nieco zmniejszyć karę wydajności, zakładając, że masz kompilator, który optymalizuje rekurencję ogona itp. (Również dwukrotnie sprawdź, czy funkcja naprawdę jest rekurencyjna - to jedna z tych rzeczy, które wiele osób popełnia błędy na.)

Oprócz przypadków „krawędziowych” (obliczenia o wysokiej wydajności, bardzo duża głębokość rekurencji itp.) Lepiej jest zastosować podejście, które najlepiej wyraża Twoje zamiary, jest dobrze zaprojektowane i możliwe do utrzymania. Zoptymalizuj dopiero po zidentyfikowaniu potrzeby.

Rekurencja jest lepsza niż iteracja w przypadku problemów, które można podzielić na wiele mniejszych części.

Na przykład, aby stworzyć rekurencyjny algorytm Fibonnaci, rozkładasz fib (n) na fib (n-1) i fib (n-2) i obliczasz obie części. Iteracja pozwala powtarzać tylko jedną funkcję w kółko.

Jednak Fibonacci jest właściwie zepsutym przykładem i myślę, że iteracja jest w rzeczywistości bardziej wydajna. Zauważ, że fib (n) = fib (n-1) + fib (n-2) i fib (n-1) = fib (n-2) + fib (n-3). Fib (n-1) jest obliczany dwukrotnie!

Lepszym przykładem jest algorytm rekurencyjny dla drzewa. Problem analizy węzła nadrzędnego można podzielić na wiele mniejszych problemów analizy każdego węzła podrzędnego. W przeciwieństwie do przykładu Fibonacciego mniejsze problemy są od siebie niezależne.

Więc tak - rekurencja jest lepsza niż iteracja dla problemów, które można podzielić na wiele mniejszych, niezależnych, podobnych problemów.

Wydajność pogarsza się podczas korzystania z rekurencji, ponieważ wywołanie metody w dowolnym języku wymaga dużo przygotowania: kod wywołujący umieszcza adres zwrotny, parametry wywołania, niektóre inne informacje kontekstowe, takie jak rejestry procesora, mogą być gdzieś zapisane, a podczas powrotu Metoda wywoływana publikuje wartość zwracaną, która jest następnie pobierana przez program wywołujący, a wszelkie zapisane wcześniej informacje kontekstowe zostaną przywrócone. różnica w wydajności między podejściem iteracyjnym a rekurencyjnym zależy od czasu, jaki zajmują te operacje.

Z punktu widzenia implementacji naprawdę zaczyna się zauważać różnicę, gdy czas potrzebny na obsługę kontekstu wywołującego jest porównywalny z czasem potrzebnym na wykonanie metody. Jeśli wykonanie metody rekurencyjnej trwa dłużej niż część zarządzania kontekstem wywołującym, przejdź w sposób rekurencyjny, ponieważ kod jest ogólnie bardziej czytelny i łatwy do zrozumienia, a nie zauważysz spadku wydajności. W przeciwnym razie przejdź iteracyjnie ze względu na wydajność.

Uważam, że rekurencja ogona w java nie jest obecnie zoptymalizowana. Szczegóły są rozproszone podczas tej dyskusji na temat LtU i powiązanych linków. Może to być funkcja w nadchodzącej wersji 7, ale najwyraźniej wiąże się to z pewnymi trudnościami w połączeniu z Inspekcją stosu, ponieważ brakuje niektórych ramek. Inspekcja stosu jest używana do implementacji ich szczegółowego modelu bezpieczeństwa od Java 2.

http://lambda-the-ultimate.org/node/1333

Istnieje wiele przypadków, w których daje to znacznie bardziej eleganckie rozwiązanie w stosunku do metody iteracyjnej, częstym przykładem jest przechodzenie przez drzewo binarne, więc niekoniecznie jest trudniejsze w utrzymaniu. Zasadniczo wersje iteracyjne są zwykle nieco szybsze (a podczas optymalizacji mogą równie dobrze zastąpić wersję rekurencyjną), ale wersje rekurencyjne są łatwiejsze do zrozumienia i prawidłowego wdrożenia.

Rekurencja jest bardzo przydatna w niektórych sytuacjach. Na przykład rozważ kod do znalezienia silni

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Rozważ to teraz za pomocą funkcji rekurencyjnej

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

Obserwując te dwa, widzimy, że rekurencja jest łatwa do zrozumienia. Ale jeśli nie jest używany ostrożnie, może być również podatny na błędy. Załóżmy, że jeśli przeoczymy if (input == 0), kod zostanie wykonany przez pewien czas i kończy się zwykle przepełnieniem stosu.

W wielu przypadkach rekurencja jest szybsza z powodu buforowania, co poprawia wydajność. Na przykład, tutaj jest iteracyjna wersja sortowania korespondencji seryjnej przy użyciu tradycyjnej procedury scalania. Będzie działał wolniej niż rekurencyjna implementacja z powodu buforowania lepszych wydajności.

Iteracyjna implementacja

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Implementacja rekurencyjna

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - tak powiedział profesor Kevin Wayne (Uniwersytet Princeton) o kursie algorytmów przedstawionych na Coursera.

Używając rekurencji, ponosisz koszt wywołania funkcji przy każdej „iteracji”, podczas gdy w pętli jedyną rzeczą, którą zwykle płacisz, jest przyrost / spadek. Jeśli więc kod dla pętli nie jest dużo bardziej skomplikowany niż kod dla rozwiązania rekurencyjnego, pętla zwykle będzie lepsza niż rekurencja.

Rekurencja i iteracja zależy od logiki biznesowej, którą chcesz wdrożyć, chociaż w większości przypadków można jej używać zamiennie. Większość programistów wybiera rekurencję, ponieważ łatwiej to zrozumieć.

To zależy od języka. W Javie powinieneś używać pętli. Języki funkcjonalne optymalizują rekurencję.

Jeśli po prostu iterujesz po liście, to na pewno iteruj dalej.

Kilka innych odpowiedzi wspomniało o przemierzaniu drzewa (w pierwszej kolejności). To naprawdę świetny przykład, ponieważ bardzo powszechną rzeczą jest wykonywanie bardzo wspólnej struktury danych. Rekurencja jest wyjątkowo intuicyjna w przypadku tego problemu.

Sprawdź metody „znajdź” tutaj: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Rekurencja jest prostsza (a zatem - bardziej fundamentalna) niż jakakolwiek możliwa definicja iteracji. Możesz zdefiniować kompletny układ Turinga za pomocą tylko pary kombinacji (tak, nawet sama rekurencja jest pojęciem pochodnym w takim systemie). Rachunek lambda jest równie potężnym systemem podstawowym, który zawiera funkcje rekurencyjne. Ale jeśli chcesz poprawnie zdefiniować iterację, na początek potrzebujesz znacznie więcej operacji podstawowych.

Jeśli chodzi o kod - nie, kod rekurencyjny jest w rzeczywistości dużo łatwiejszy do zrozumienia i utrzymania niż kod czysto iteracyjny, ponieważ większość struktur danych jest rekurencyjna. Oczywiście, aby wszystko było w porządku, potrzebny byłby język z obsługą przynajmniej funkcji i zamknięć wyższego rzędu - aby uzyskać wszystkie standardowe kombinatory i iteratory w zgrabny sposób. Oczywiście w C ++ skomplikowane rozwiązania rekurencyjne mogą wyglądać nieco brzydko, chyba że jesteś zapalonym użytkownikiem FC ++ i tym podobnych.

Myślałem, że w rekurencji (nie ogonowej) za każdym razem, gdy wywoływana jest funkcja, pojawiłby się błąd wydajności przy przydzielaniu nowego stosu (oczywiście w zależności od języka).

zależy to od „głębokości rekurencji”. zależy to od tego, jak bardzo narzut wywołania funkcji wpłynie na całkowity czas wykonania.

Na przykład obliczanie klasycznej silni w sposób rekurencyjny jest bardzo nieefektywne z powodu: - ryzyka przepełnienia danych - ryzyka przepełnienia stosu - narzut wywołania funkcji zajmuje 80% czasu wykonania

podczas opracowywania algorytmu min-max do analizy pozycji w grze w szachy, który analizuje kolejne N ruchów, można zastosować w rekurencji na „głębokości analizy” (tak jak robię ^ _ ^)

Rekurencja? Od czego zacząć, wiki powie ci „to proces powtarzania przedmiotów w podobny sposób”

W czasach, gdy robiłem C, rekurencja w C ++ była wysyłana przez boga, takie rzeczy jak „rekursja ogona”. Znajdziesz również wiele algorytmów sortowania wykorzystujących rekurencję. Przykład szybkiego sortowania: http://alienryderflex.com/quicksort/

Rekurencja jest jak każdy inny algorytm przydatny w przypadku konkretnego problemu. Być może nie możesz znaleźć zastosowania od razu lub często, ale będzie problem, z którego będziesz zadowolony.

W C ++, jeśli funkcja rekurencyjna jest szablonowa, to kompilator ma większą szansę na jej optymalizację, ponieważ wszystkie dedukcje typów i instancje funkcji wystąpią w czasie kompilacji. Nowoczesne kompilatory mogą również wbudować funkcję, jeśli to możliwe. Więc jeśli ktoś używa flag optymalizacji takich jak -O3lub -O2wg++ , a następnie rekursji może mieć szansę być szybciej niż iteracji. W kodach iteracyjnych kompilator ma mniejszą szansę na jego optymalizację, ponieważ jest już w mniej lub bardziej optymalnym stanie (jeśli jest wystarczająco dobrze napisany).

W moim przypadku próbowałem zaimplementować potęgowanie macierzy poprzez podniesienie kwadratu za pomocą obiektów macierzy Armadillo, zarówno w sposób rekurencyjny, jak i iteracyjny. Algorytm można znaleźć tutaj ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Moje funkcje były szablonowane i obliczyłem 1,000,000 12x12macierze podniesione do potęgi 10. Mam następujący wynik:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Te wyniki zostały uzyskane przy użyciu gcc-4.8 z flagą c ++ 11 ( -std=c++11) i Armadillo 6.1 z Intel mkl. Kompilator Intel pokazuje również podobne wyniki.

Mike ma rację. Rekurencja ogona nie jest zoptymalizowana przez kompilator Java lub JVM. Zawsze otrzymasz przepełnienie stosu z czymś takim:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Należy pamiętać, że przy zbyt głębokiej rekurencji napotkasz przepełnienie stosu, w zależności od dozwolonego rozmiaru stosu. Aby temu zapobiec, zapewnij podstawową skrzynkę, która zakończy rekursję.

Wadą jest to, że algorytm, który piszesz przy użyciu rekurencji, ma złożoność przestrzeni O (n). Chociaż iteracyjne podejście ma złożoność przestrzenną O (1), jest to zaleta używania iteracji nad rekurencją. Dlaczego więc używamy rekurencji?

Patrz poniżej.

Czasami łatwiej jest napisać algorytm przy użyciu rekurencji, podczas gdy nieco trudniej jest napisać ten sam algorytm przy użyciu iteracji. W takim przypadku, jeśli zdecydujesz się na podejście iteracyjne, będziesz musiał sam sobie poradzić ze stosem.

Jeśli iteracje są atomowe, a rzędy wielkości są droższe niż wypychanie nowej ramki stosu i tworzenie nowego wątku, a masz wiele rdzeni i środowisko wykonawcze może korzystać z nich wszystkich, wówczas podejście rekurencyjne może zapewnić ogromny wzrost wydajności w połączeniu z wielowątkowość. Jeśli średniej liczby iteracji nie da się przewidzieć, dobrym pomysłem może być użycie puli wątków, która będzie kontrolować przydział wątków i zapobiegać tworzeniu przez proces zbyt wielu wątków i blokowaniu systemu.

Na przykład w niektórych językach istnieją rekurencyjne wielowątkowe implementacje sortowania scalającego.

Ale znowu wielowątkowość może być używana z zapętlaniem, a nie rekurencją, więc to, jak dobrze ta kombinacja będzie działać, zależy od większej liczby czynników, w tym systemu operacyjnego i mechanizmu alokacji wątków.

O ile mi wiadomo, Perl nie optymalizuje połączeń rekurencyjnych, ale możesz to sfałszować.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

Po pierwszym wywołaniu przydzieli miejsce na stosie. Następnie zmieni swoje argumenty i zrestartuje podprogram, nie dodając nic więcej do stosu. Dlatego będzie udawać, że nigdy nie wezwał siebie, zmieniając go w proces iteracyjny.

Zauważ, że nie ma „ my @_;” lub „ local @_;”, jeśli to zrobisz, przestanie działać.

Używając zaledwie Chrome 45.0.2454,85 ​​m, rekurencja wydaje się być o wiele szybsza.

Oto kod:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

WYNIKI

// 100 działa przy użyciu standardowej pętli for

100x dla pracy w pętli. Czas na ukończenie: 7,683 ms

// 100 przebiegów przy użyciu funkcjonalnego podejścia rekurencyjnego z rekurencją ogona

100-krotny cykl rekurencyjny. Czas na ukończenie: 4,841 ms

Na poniższym zrzucie ekranu rekurencja wygrywa ponownie o większy margines, gdy jest uruchamiana przy 300 cyklach na test

Znalazłem inne różnice między tymi podejściami. Wygląda na prosty i nieważny, ale ma bardzo ważną rolę podczas przygotowywania się do wywiadów i ten temat powstaje, więc przyjrzyj się uważnie.

W skrócie: 1) iteracyjne przechodzenie po zamówieniu nie jest łatwe - to sprawia, że ​​DFT jest bardziej złożone 2) sprawdzanie cykli z rekurencją

Detale:

W przypadku rekurencyjnym łatwo jest tworzyć przejścia przed i po:

Wyobraź sobie dość standardowe pytanie: „wydrukuj wszystkie zadania, które powinny zostać wykonane, aby wykonać zadanie 5, gdy zadania zależą od innych zadań”

Przykład:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Należy zauważyć, że rekurencyjne przechodzenie po zamówieniu nie wymaga późniejszego odwrócenia wyniku. Dzieci drukowane jako pierwsze, a twoje zadanie w pytaniu drukowane jako ostatnie. Wszystko w porządku. Możesz wykonać rekursywne przechodzenie przed zamówieniem (również pokazane powyżej), które będzie wymagało odwrócenia listy wyników.

Nie jest to takie proste z iteracyjnym podejściem! W podejściu iteracyjnym (jeden stos) możesz wykonać tylko przechodzenie w przedsprzedaży, więc musisz odwrócić tablicę wyników na końcu:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Wygląda prosto, nie?

Ale w niektórych wywiadach jest to pułapka.

Oznacza to, że: stosując podejście rekurencyjne, możesz wdrożyć Głębokość Najpierw przemieszczenie, a następnie wybrać, jakiej kolejności potrzebujesz przed lub po (zmieniając położenie „wydruku”, w naszym przypadku „dodawania do listy wyników” ). Dzięki iteracyjnemu podejściu (jeden stos) możesz łatwo zrobić tylko przejście w przedsprzedaży, a więc w sytuacji, gdy dzieci muszą być najpierw wydrukowane (prawie wszystkie sytuacje, gdy potrzebujesz rozpocząć drukowanie od dolnych węzłów, idąc w górę) - jesteś w problem. Jeśli masz takie problemy, możesz później je odwrócić, ale będzie to dodatek do Twojego algorytmu. A jeśli ankieter patrzy na zegarek, może to stanowić dla ciebie problem. Istnieją złożone sposoby iteracyjnego przechodzenia po zamówieniu, istnieją, ale nie są proste . Przykład:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Podsumowując: użyłbym rekurencji podczas wywiadów, łatwiej jest zarządzać i wyjaśniać. W każdej pilnej sprawie masz łatwy sposób na przejście od zamówienia przed i po zamówieniu. Dzięki iteracji nie jesteś tak elastyczny.

Użyłbym rekurencji, a następnie powiedziałbym: „Ok, ale iteracja może zapewnić mi bardziej bezpośrednią kontrolę nad używaną pamięcią, mogę łatwo zmierzyć rozmiar stosu i zapobiec niebezpiecznemu przepełnieniu…”

Kolejny plus rekurencji - łatwiej jest unikać / zauważać cykle na wykresie.

Przykład (preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Pisanie go jako rekurencji lub jako praktyki może być zabawne.

Jeśli jednak kod ma być wykorzystywany w produkcji, należy wziąć pod uwagę możliwość przepełnienia stosu.

Optymalizacja rekurencji ogona może wyeliminować przepełnienie stosu, ale czy chcesz sobie z tym poradzić, i musisz wiedzieć, że możesz liczyć na optymalizację w swoim środowisku.

Ile razy rozmiar danych jest nzmniejszany za każdym razem, gdy algorytm się powtarza ?

Jeśli zmniejszasz rozmiar danych lub no połowę za każdym razem, gdy się powtórzysz, to na ogół nie musisz się martwić o przepełnienie stosu. Powiedzmy, że jeśli program musi przepełnić 4000 poziomów lub 10 000 poziomów głębokości, aby program mógł przepełnić stos, wówczas rozmiar danych musi wynosić około 2 ^4000, aby program mógł przepełnić stos. Aby spojrzeć na to z perspektywy, największe urządzenie pamięci masowej może ostatnio pomieścić 2 ⁶¹ bajtów, a jeśli masz 2 ⁶¹ takich urządzeń, masz do czynienia tylko z wielkością 2 ¹²² danych. Jeśli patrzysz na wszystkie atomy we wszechświecie, szacuje się, że może to być mniej niż 2 ⁸⁴. Jeśli musisz poradzić sobie ze wszystkimi danymi we wszechświecie i ich stanami dla każdej milisekundy od narodzin wszechświata szacowanego na 14 miliardów lat temu, może to być tylko 2 ¹⁵³ . Więc jeśli twój program może obsłużyć 2 ⁴⁰⁰⁰ jednostek danych lub nmożesz obsłużyć wszystkie dane we wszechświecie, a program nie będzie stosy przepełnienia. Jeśli nie musisz zajmować się liczbami tak dużymi jak 2 ⁴⁰⁰⁰ (4000-bitowa liczba całkowita), to na ogół nie musisz się martwić o przepełnienie stosu.

Jeśli jednak zmniejszysz rozmiar danych lub no stałą ilość za każdym razem, gdy się powtórzysz, możesz napotkać przepełnienie stosu, gdy program działa dobrze, gdy njest, 1000ale w pewnych sytuacjach, gdy nstaje się po prostu 20000.

Jeśli więc istnieje możliwość przepełnienia stosu, spróbuj uczynić go iteracyjnym rozwiązaniem.

Odpowiem na twoje pytanie, projektując strukturę danych Haskell poprzez „indukcję”, która jest rodzajem „podwójnej” rekurencji. A potem pokażę, jak ta dualność prowadzi do miłych rzeczy.

Przedstawiamy typ prostego drzewa:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

Możemy odczytać tę definicję mówiącą: „Drzewo to gałąź (która zawiera dwa drzewa) lub liść (zawierający wartość danych)”. Liść jest więc rodzajem minimalnego przypadku. Jeśli drzewo nie jest liściem, musi to być drzewo złożone zawierające dwa drzewa. To są jedyne przypadki.

Zróbmy drzewo:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Załóżmy teraz, że chcemy dodać 1 do każdej wartości w drzewie. Możemy to zrobić, dzwoniąc:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

Po pierwsze, zauważ, że jest to w rzeczywistości rekurencyjna definicja. Konstruktorzy danych Rozgałęzianie i Liście traktują jako przypadki (a ponieważ Leaf jest minimalny i są to jedyne możliwe przypadki), jesteśmy pewni, że funkcja się zakończy.

Co zajęłoby napisanie addOne w iteracyjnym stylu? Jak będzie wyglądało zapętlenie dowolnej liczby oddziałów?

Ponadto tego rodzaju rekurencję można często rozłożyć na czynniki, pod względem „funktora”. Możemy przekształcić Drzewa w Functors, definiując:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

i definiowanie:

addOne' = fmap (+1)

Możemy wyróżnić inne schematy rekurencji, takie jak katamorfizm (lub fałd) dla algebraicznego typu danych. Za pomocą katamorfizmu możemy napisać:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

Przepełnienie stosu nastąpi tylko wtedy, gdy programujesz w języku, który nie ma wbudowanego zarządzania pamięcią ... W przeciwnym razie upewnij się, że masz coś w swojej funkcji (lub wywołanie funkcji, STDLbs itp.). Bez rekurencji po prostu nie byłoby możliwe, aby mieć takie rzeczy jak ... Google, SQL lub inne miejsce, w którym trzeba efektywnie sortować duże struktury danych (klasy) lub bazy danych.

Rekurencja jest właściwym rozwiązaniem, jeśli chcesz wykonywać iteracje po plikach, całkiem pewne, że właśnie tak „znajdź * | działa? grep * '. Trochę podwójna rekurencja, szczególnie z potokiem (ale nie rób wielu wywołań systemowych, jak wielu, którzy lubią robić, jeśli chcesz coś udostępnić innym).

Języki wyższego poziomu, a nawet clang / cpp mogą implementować to samo w tle.