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ć?

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.

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ę ⁺ .

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ź .

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.

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)); 
   }
}

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).

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”.

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.

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

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