rekurencja a iteracja


109

Czy słuszne jest stwierdzenie, że wszędzie tam, gdzie używana jest rekurencja, można użyć forpętli? A jeśli rekurencja jest zwykle wolniejsza, jaki jest techniczny powód, aby kiedykolwiek używać jej forzamiast iteracji pętli?

A jeśli zawsze jest możliwe przekształcenie rekurencji w forpętlę, czy istnieje praktyczna zasada, aby to zrobić?


3
recursionvs iteration? iteration = for loopMyślę.
gongzhitaao,

4
Blog Toma Moertela zawiera cztery doskonałe posty na temat konwersji kodu rekurencyjnego do kodu iteracyjnego: blog.moertel.com/tags/recursion.html
cjohnson318

Odpowiedzi:


148

Rekurencja jest zwykle znacznie wolniejsza, ponieważ wszystkie wywołania funkcji muszą być przechowywane na stosie, aby umożliwić powrót do funkcji wywołującej. W wielu przypadkach pamięć musi zostać przydzielona i skopiowana w celu zaimplementowania izolacji zakresu.

Niektóre optymalizacje, takie jak optymalizacja wywołań końcowych , przyspieszają rekurencje, ale nie zawsze są możliwe i nie są zaimplementowane we wszystkich językach.

Główne powody korzystania z rekurencji to

  • że jest bardziej intuicyjny w wielu przypadkach, gdy naśladuje nasze podejście do problemu
  • że niektóre struktury danych, takie jak drzewa, są łatwiejsze do zbadania przy użyciu rekurencji (lub w każdym przypadku wymagałyby stosów)

Oczywiście każdą rekursję można zamodelować jako rodzaj pętli: to ostatecznie zrobi procesor. A sama rekurencja, bardziej bezpośrednio, oznacza umieszczenie wywołań funkcji i zakresów na stosie. Jednak zmiana algorytmu rekurencyjnego na algorytm zapętlający może wymagać dużo pracy i sprawić, że kod będzie trudniejszy do utrzymania: tak jak w przypadku każdej optymalizacji, należy próbować tego dokonać tylko wtedy, gdy niektóre profilowanie lub dowody wykazały, że jest to konieczne.


10
Aby dodać do tego - rekurencja jest ściśle związana z pojęciem redukcji, które odgrywa kluczową rolę w wielu algorytmach i ogólnie w CS.
SomeWittyUsername

3
Czy możesz podać przykład, w którym rekurencja sprawia, że ​​kod jest łatwiejszy w utrzymaniu? Z mojego doświadczenia wynika, że ​​zawsze jest odwrotnie. Dziękuję
Yeikel,

@Yeikel Napisz funkcję, f(n)która zwraca n-tą liczbę Fibonacciego .
Matt,

54

Czy można powiedzieć, że wszędzie tam, gdzie jest używana rekurencja, można użyć pętli for?

Tak, ponieważ rekurencja w większości procesorów jest modelowana za pomocą pętli i struktury danych stosu.

A jeśli rekurencja jest zwykle wolniejsza, jaki jest techniczny powód jej używania?

Nie jest to „zwykle wolniejsze”: to rekurencja, która jest stosowana nieprawidłowo, jest wolniejsza. Co więcej, nowoczesne kompilatory są dobre w konwertowaniu niektórych rekurencji na pętle bez pytania.

A jeśli zawsze jest możliwe przekonwertowanie rekurencji na pętlę for, czy istnieje praktyczna zasada, aby to zrobić?

Napisz programy iteracyjne dla algorytmów najlepiej zrozumiałych, gdy zostaną wyjaśnione iteracyjnie; pisać programy rekurencyjne dla algorytmów najlepiej wyjaśnionych rekurencyjnie.

Na przykład wyszukiwanie drzew binarnych, uruchamianie szybkiego sortowania i analizowanie wyrażeń w wielu językach programowania jest często wyjaśniane rekurencyjnie. Te są również najlepiej kodowane rekurencyjnie. Z drugiej strony obliczanie silni i obliczanie liczb Fibonacciego jest znacznie łatwiejsze do wyjaśnienia za pomocą iteracji. Używanie rekurencji jest dla nich jak uderzanie much młotem kowalskim: to nie jest dobry pomysł, nawet jeśli młot robi naprawdę dobrą robotę + .


+ Zapożyczyłem analogię młota kowalskiego z „Dyscypliny programowania” Dijkstry.


7
Rekurencja jest zwykle droższa (wolniejsza / więcej pamięci) z powodu tworzenia ramek stosu i tym podobnych. Różnica może być niewielka, jeśli zastosuje się ją prawidłowo dla wystarczająco złożonego problemu, ale nadal jest droższa. Istnieją możliwe wyjątki, takie jak optymalizacja rekurencji ogona.
Bernhard Barker

Nie jestem pewien co do pojedynczej pętli for w każdym przypadku. Rozważ bardziej złożoną rekursję lub rekursję z więcej niż jedną zmienną
SomeWittyUsername

@dasblinkenlight Teoretycznie możliwe jest zredukowanie wielu pętli do jednej, ale nie jestem tego pewien.
SomeWittyUsername

@icepack Tak, jest to możliwe. Może nie jest to ładne, ale jest możliwe.
Bernhard Barker

Nie jestem pewien, czy zgadzam się z pierwszym stwierdzeniem. Same procesory tak naprawdę w ogóle nie modelują rekurencji, to instrukcje uruchamiane na procesorze modelują rekursję. po drugie, struktura pętli nie ma (koniecznie) dynamicznie rosnącego i kurczącego się zbioru danych, przy czym algorytm rekurencyjny zwykle będzie wymagał przejścia rekursji na każdym poziomie głęboko.
trumpetlicks

29

Pytanie 30:

A jeśli rekurencja jest zwykle wolniejsza, jaki jest techniczny powód, aby kiedykolwiek używać jej do iteracji pętli?

Odpowiedź :

Ponieważ w niektórych algorytmach trudno jest rozwiązać to iteracyjnie. Spróbuj rozwiązać przeszukiwanie w głąb zarówno rekurencyjnie, jak i iteracyjnie. Pojawi się pomysł, że po prostu trudno jest rozwiązać DFS za pomocą iteracji.

Kolejna dobra rzecz do wypróbowania: spróbuj napisać sortowanie według scalania iteracyjnie. Zajmie ci to trochę czasu.

Pytanie 30:

Czy można powiedzieć, że wszędzie tam, gdzie jest używana rekurencja, można użyć pętli for?

Odpowiedź :

Tak. Ten wątek ma na to bardzo dobrą odpowiedź.

Pytanie 30:

A jeśli zawsze jest możliwe przekonwertowanie rekurencji na pętlę for, czy istnieje praktyczna zasada, aby to zrobić?

Odpowiedź :

Zaufaj mi. Spróbuj napisać własną wersję, aby iteracyjnie rozwiązywać wyszukiwanie w głąb. Zauważysz, że niektóre problemy są łatwiejsze do rozwiązania rekurencyjnego.

Wskazówka: Rekurencja jest dobra, gdy rozwiązujesz problem, który można rozwiązać za pomocą techniki dziel i rządź .


3
Doceniam próbę udzielenia miarodajnej odpowiedzi i jestem pewien, że autor jest inteligentny, ale „zaufaj mi” nie jest pomocną odpowiedzią na sensowne pytanie, na które odpowiedź nie jest od razu oczywista. Istnieją bardzo proste algorytmy wykonywania iteracyjnego przeszukiwania w głąb. Zobacz przykład na dole tej strony, aby zapoznać się
jdelman

3

Oprócz tego, że jest wolniejsza, rekursja może również powodować błędy przepełnienia stosu w zależności od tego, jak głęboko sięga.


3

Aby napisać równoważną metodę za pomocą iteracji, musimy jawnie użyć stosu. Fakt, że wersja iteracyjna wymaga stosu do rozwiązania, wskazuje, że problem jest na tyle trudny, że może skorzystać na rekursji. Zgodnie z ogólną zasadą rekurencja jest najbardziej odpowiednia w przypadku problemów, których nie można rozwiązać przy użyciu określonej ilości pamięci, a co za tym idzie, gdy są rozwiązywane iteracyjnie, wymagają stosu. To powiedziawszy, rekurencja i iteracja mogą dawać ten sam wynik, ale podążają za innym wzorcem. Aby zdecydować, która metoda działa lepiej, należy w każdym przypadku, a najlepszą praktyką jest wybór na podstawie wzorca, za którym podąża problem.

Na przykład, aby znaleźć n-tą liczbę trójkątną sekwencji trójkątnej: 1 3 6 10 15… Program, który używa iteracyjnego algorytmu do znalezienia n-tej liczby trójkątnej:

Korzystanie z algorytmu iteracyjnego:

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

Korzystanie z algorytmu rekurencyjnego:

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

1

Większość odpowiedzi wydaje się zakładać, że iterative= for loop. Jeśli twoja pętla for jest nieograniczona ( a la C, możesz robić, co chcesz z licznikiem pętli), to jest poprawne. Jeśli jest to prawdziwa for pętla (powiedzmy jak w Pythonie lub większości języków funkcyjnych, gdzie nie można ręcznie modyfikować licznik pętli), to nie poprawne.

Wszystkie (obliczalne) funkcje mogą być implementowane zarówno rekurencyjnie, jak i przy użyciu whilepętli (lub skoków warunkowych, które są w zasadzie tym samym). Jeśli naprawdę ograniczysz się do for loops, otrzymasz tylko podzbiór tych funkcji (prymitywne funkcje rekurencyjne, jeśli twoje podstawowe operacje są rozsądne). To prawda, jest to dość duży podzbiór, który zawiera każdą funkcję, którą prawdopodobnie będziesz szyfrować w praktyce.

O wiele ważniejsze jest to, że wiele funkcji jest bardzo łatwych do implementacji rekurencyjnie i strasznie trudnych do implementacji iteracyjnej (ręczne zarządzanie stosem wywołań się nie liczy).


1

Tak, jak powiedział przez Thanakron Tandavas ,

Rekursja jest dobra, gdy rozwiązujesz problem, który można rozwiązać za pomocą techniki dziel i zwyciężaj.

Na przykład: Wieże Hanoi

  1. Pierścienie N w coraz większym rozmiarze
  2. 3 bieguny
  3. Pierścienie zaczynają się układać na słupie 1. Celem jest przesunięcie pierścieni tak, aby były ułożone na słupie 3 ... Ale
    • Jednocześnie można przesuwać tylko jeden pierścień.
    • Nie można umieścić większego pierścienia na mniejszym.
  4. Rozwiązanie iteracyjne jest „potężne, ale brzydkie”; rozwiązanie rekurencyjne jest „eleganckie”.

Ciekawy przykład. Chyba znasz artykuł MC Er „Wieże Hanoi i cyfry binarne”. Również traktowane w fantastycznym filmie 3brown1blue.
Andrestand

0

Wydaje mi się, że mój profesor informatyki powiedział kiedyś, że wszystkie problemy, które mają rozwiązania rekurencyjne, mają również rozwiązania iteracyjne. Mówi, że rozwiązania rekurencyjne są zwykle wolniejsze, ale są często używane, gdy łatwiej jest z nimi rozumować i kodować niż rozwiązania iteracyjne.

Jednak w przypadku bardziej zaawansowanych rozwiązań rekurencyjnych nie wierzę, że zawsze da się je zaimplementować za pomocą prostej forpętli.


Zawsze jest możliwe przekonwertowanie algorytmu rekurencyjnego na iteracyjny (przy użyciu stosów). Możesz nie otrzymać szczególnie prostej pętli, ale jest to możliwe.
Bernhard Barker

-4

rekurencja + zapamiętywanie może prowadzić do bardziej wydajnego rozwiązania w porównaniu z podejściem czysto iteracyjnym, np. sprawdź to: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n


3
Każdy kod rekurencyjny można przekonwertować na identyczny funkcjonalnie kod iteracyjny przy użyciu stosów. Różnica, którą pokazujesz, to różnica między dwoma podejściami do rozwiązania tego samego problemu, a nie różnica między rekurencją a iteracją.
Bernhard Barker

-6

Krótka odpowiedź: kompromisem jest to, że rekurencja jest szybsza, a pętle zajmują mniej pamięci w prawie wszystkich przypadkach. Jednak zazwyczaj istnieją sposoby na zmianę pętli for lub rekurencji, aby działała szybciej

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.