Jaka jest różnica między iteracją a rekurencją?
Jaka jest różnica między iteration a recursion i dlaczego/kiedy jest lepiej:
while (true) {
// Iterating
}
I
private void recursion() {
if (true)
recursion(); // Recursing
return;
}
Widzę wiele recursive implementacji, podczas gdy można to łatwo zrobić w prostej pętli.
8 answers
Istnieją dwie główne różnice między Rekurencją a iteracyjną wersją tego samego algorytmu.
Po pierwsze, Czasami jest prawie lepiej zrozumieć algorytm rekurencyjny niż iteracyjny (przynajmniej jeśli jesteś doświadczonym programistą) , więc Zwiększa to wyrazistość i w niektórych przypadkach czytelność (może również prowadzić do dokładnego przeciwieństwa w innych przypadkach)
Expresivity to ogromna oferta na języki programowania i być w stanie napisać ten sam kod w 5 linijkach zamiast 20 to wielka sprawa.
Z drugiej strony, zmniejsza to wydajność Twojego kodu. Funkcje rekurencyjne muszą przechowywać rekordy funkcji w pamięci i przeskakiwać z jednego adresu pamięci do drugiego, aby być wywołane w celu przekazania parametrów i wartości zwrotnych. To czyni je bardzo kiepskimi.
Suma:
Algorytmy iteracyjne = Szybka wydajność, ale trudna do napisania (czasami trudna do odczytania)
Algorytmy rekurencyjne = szybkie do napisania, ale złe wydajność mądry (czasami łatwiej zrozumieć zbyt)
Weźmy ten przykład:
public static long fib(long n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
Vs
if ((n == 1) || (n == 2)) {
return 1;
} else {
long prev = 1, current = 1, next = 0;
for (long i = 3; i <= n; i++) {
next = prev + current;
prev = current;
current = next;
}
return next;
}
Źródło:
Http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-25 03:31:00
Główną różnicą między rekurencją a iteracją jest użycie pamięci.
Dla każdego wywołania rekurencyjnego potrzeba miejsca na ramce stosu, co skutkuje narzutem pamięci.
Dam ci przykład. Wyobraź sobie, że w jednym przypadku zapomniałeś napisać podstawową literę dla swojej funkcji rekurencyjnej, co skutkuje nieskończonymi wywołaniami rekurencyjnymi, a w innym przypadku napisałeś nieskończoną pętlę.
Ponieważ każda funkcja rekurencyjna przypisuje nową przestrzeń pamięci, w pierwszym przypadku twój kod da przepełnienie stosu wyjątek, ale w drugim przypadku będzie działać na zawsze.
Więc lepiej uczynić kod iteracyjny bardziej zrozumiałym niż użyć rekurencji.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-10-08 15:59:10
Są to różne sposoby na zrobienie tego samego. Wszystkie implementacje rekurencyjne mogą być wykonywane za pomocą pętli (lub wielu) i odwrotnie. Chodzi bardziej o logikę, która za tym stoi, sposób myślenia o tym. Factorial, choć nie jest najlepszym przykładem, jest n * (n-1)! więc ma sens używać go rekurencyjnie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-11-05 17:14:49
Rekurencja i iteracja to różne sposoby myślenia o rozwiązaniu. Dokładne wyjaśnienie różnic w pełnym zakresie byłoby trudne. W przykładowym kodzie pokazałeś różnicę. Funkcja rekurencyjna to ta, która wywołuje samą siebie, podczas gdy iteracyjna to ta, która zapętla jakiś blok kodu. Oto kilka artykułów, które pomogą Ci lepiej je zrozumieć: recursion wiki
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:34:43
Mogą być używane wymiennie do rozwiązywania różnych problemów. Zasadniczo można pisać funkcje rekurencyjne iteracyjnie i odwrotnie.
Iteracja może zwiększyć wydajność Twojego programu. Natomiast rekurencja może dać bardziej intuicyjny i elegancki wynik. Możesz wybrać albo który do swoich preferencji!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-11-05 17:20:54
Funkcje rekurencyjne działają poprzez proces wywoływania się do momentu spełnienia warunku, podczas gdy iteracja używa pętli kontrolnej (na przykład while, do while, for) w celu powtórzenia sekcji kodu do momentu spełnienia określonego warunku.
Przykład rekurencyjny:
int rec_func(int u, int k) {
if (k == 0)
return u;
return rec_func(u * k, k - 1);
}
Przykład iteracji:
int ite_func(int u, int k) {
while (k != 0) {
u = u * k;
k = k - 1;
}
return u;
}
Jedyną prawdziwą różnicą pomiędzy nimi są różnice kompilacji.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-11-05 17:21:44
Teoretycznie zawsze można zamienić iterację na rekurencję. Jednakże, przynajmniej w przypadku C/C++/C#/Java, kompilator oferuje pewne wsparcie, które może uczynić rozwiązanie bardziej eleganckim, zwłaszcza gdy nie znasz wcześniej liczby pętli.
Najlepszym przykładem jest lista wszystkich plików wewnątrz folderu i jego potomków. Jeśli istnieje kilka podfolderów składających się z podfolderów, zwykle w trybie iteracji potrzebny jest stos do zapisania wszystkich folderów do analizy. W przypadku podejście rekurencyjne, stos jest już dostarczany przez kompilator, a rozwiązanie jest bardziej eleganckie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-08-25 10:14:16
Różnice między rekurencją a iteracją
Rekurencja
- funkcja rekurencyjna - jest funkcją częściowo zdefiniowaną przez siebie
- Rekurencja wykorzystuje strukturę selekcji
- rekurencja nieskończona występuje, jeśli krok rekurencyjny nie zmniejsza problemu w sposób zbieżny pod pewnym warunkiem (wielkość liter)
- Rekurencja kończy się, gdy rozpoznawany jest przypadek podstawowy
- Rekurencja jest zwykle wolniejsza niż iteracja ze względu na utrzymanie stosu
- Rekurencja wykorzystuje więcej pamięci niż iteracja
- nieskończona rekurencja może spowodować awarię systemu
- Rekurencja sprawia, że kod jest mniejszy
Iteracja
- instrukcje iteracyjne - są powtórzeniami procesu opartego na pętli
- iteracja wykorzystuje strukturę powtórzeń
- pętla nieskończona występuje z iteracją, jeśli test warunku pętli nigdy nie będzie fałszywy
- iteracja kończy się, gdy warunek pętli fails
- iteracja nie używa stosu, więc jest szybsza niż rekurencja
- iteracja zużywa mniej pamięci
- nieskończona pętla wykorzystuje wielokrotnie cykle procesora
- iteracja wydłuża kod
Dane pobrane z tutaj .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-19 17:19:59