Czy wszystkie funkcje rekurencyjne mogą być kodowane za pomocą iteracji? [Zamknięte]

10

Jakie są zalety rekurencji?

Niektóre języki programowania mogą zoptymalizować rekurencję ogona, ale nadal ogólnie rekurencja zużywa więcej zasobów niż zwykłe pętle.

Czy można mieć iteracyjną wersję niektórych funkcji rekurencyjnych?

OscarRyz
źródło

Odpowiedzi:

10

Tak, możesz kodować funkcje rekurencyjne jako iteracje. Zasadniczo wymaga ręcznego przechowywania informacji, które w innym przypadku zostałyby załatwione przez kod wywołujący metodę wygenerowany przez kompilator.

Innymi słowy, potrzebujesz stosu, w którym każdy wpis jest strukturą zawierającą przekazane parametry i wszystkie zmienne lokalne. Zawsze pracujesz nad najwyższym wpisem na stosie. Jeśli musisz zadzwonić, utwórz nowy wpis i umieść na stosie. Po zakończeniu weź najwyższy wpis stosu, odsłaniając poniższy, i użyj poprzednio najwyższego wpisu, aby wyodrębnić zwracane wartości i odpowiednio zaktualizować nowy najwyższy wpis.

Sugeruję przestudiowanie książki kompilatora, aby zobaczyć, jak zwykle jest to zaimplementowane w kodzie maszynowym.


źródło
Rozumiem. Jaką przewagę miałaby rekurencja? Prostota?
OscarRyz
2
@OscarRyz: Tak, i jest bardziej elegancki.
Michael K,
@OscarRyz, sposób Opisałem to rekurencji. Po prostu nie jest to wykonywane przy użyciu natywnych instrukcji procesora. Wykonanie tego ręcznie pozwala wykonywać różne czynności - na przykład równoległe - które źle odwzorowują instrukcje natywne.
15

Rekurencja jest często bardziej naturalnym sposobem patrzenia na rzeczy niż iteracja. Rozważmy na przykład przechodzenie przez drzewo binarne: inorder(left); process(); inorder(right);jest o wiele prostsze niż jawne utrzymywanie stosu.

Tak długo, jak nie wchodzisz zbyt głęboko (wysadzenie stosu), różnica w wykorzystaniu zasobów jest zwykle trywialna. Nie przejmuj się tym ogólnie. Zwykły kod jest zwykle lepszy niż kod zoptymalizowany ręcznie, choć są wyjątki. Prawo jest zwykle lepsze niż szybkie.

Każdy algorytm rekurencyjny może być wyrażony jako algorytm iteracyjny, ale może być konieczne zachowanie jawnego stosu (odpowiadającego stosowi wywołań, który jest obsługiwany niejawnie). W końcu, jeśli skompilujesz funkcję rekurencyjną, otrzymasz coś, co polega na manipulowaniu stosem i zapętlaniu funkcji, i to jest iteracja.

Funkcje rekurencyjne mogą być łatwo przetłumaczone na pętle i nie wymagają stosu, ale jest to szczególny przypadek.

David Thornley
źródło
8
Powiedziałbym, że racja jest zawsze lepsza niż szybka. Kod, który szybko robi źle, nie jest dla nikogo zbyt dobry.
Mason Wheeler,
1
Ale co, jeśli możesz zrobić to źle naprawdę szybko ?!
RationalGeek,
1
@jkohlhepp - Mogę natychmiast rozwiązać każdy problem. Odpowiedź brzmi: 0
Uwaga, aby pomyśleć o nazwie
2
Użycie rekurencji zamiast jawnego stosu może być bardziej wydajne - unikając konieczności alokacji sterty, możliwej fragmentacji pamięci i możliwych problemów z lokalizacją. Jednak w przypadku opcji „prawo jest zwykle lepsze niż szybkie” przepełnienie stosu w przypadkach, w których oprogramowanie musi obsługiwać, oznacza uszkodzenie kodu. Zwykle przypadki problemów są dość łatwe do wykrycia - rekurencja na (rozsądnie) zrównoważonym drzewie jest w porządku, ale rekurencja na drzewie, które może być bardzo niezrównoważone lub na połączonej liście, może być poważnym błędem w języku takim jak C. Worse , może przetrwać proste testy i zawieszać się tylko przy prawdziwym wdrożeniu.
Steve314,
1
Myślę, że wszyscy rozumiecie, co miał na myśli Mason i żartujecie sobie z tego dla zabawy. Oczywiście powolny poprawny program jest bardziej przydatny niż szybki niepoprawny program.
Giorgio
4

Jakie są zalety rekurencji?

Spróbuj iteracyjnie rozwiązać problem z Wieżami Hanoi. Po poddaniu się, spójrz na iteracyjne rozwiązanie i porównaj je z rekurencyjnym. Który jest prostszy?

Czy można mieć iteracyjną wersję niektórych funkcji rekurencyjnych?

Tak, w zasadzie. Jednak w przypadku wielu problemów, w tym bardzo typowych zadań, takich jak przechodzenie przez drzewa, rozwiązania rekurencyjne są znacznie prostsze i bardziej eleganckie niż iteracyjne.

Dima
źródło
3

Jakie są zalety rekurencji?

Prostota. Bez optymalizacji wywołania ogonowego wymaga to oczywiście więcej zasobów (stosu), ale jak zaimplementowałbyś, powiedzmy, deltreew Javie bez rekurencji? Rzecz w tym, że delete()można usuwać katalogi tylko wtedy, gdy są puste; oto z rekurencją:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
Joonas Pulakka
źródło
1
Ze stosem, jak wspomniano w innych odpowiedziach.
Nicole,
Tak, ale jakie to proste? -)
Joonas Pulakka,
Och, rekurencja jest zdecydowanie lepsza. Myślałem, że mówisz, że to niemożliwe.
Nicole,
0

Uważam, że rekurencja jest jednym z tych narzędzi, które musi mieć programista . Za pomocą rekurencji możesz „myśleć” o swoich algorytmach i rozwiązywać je tak, jak o tym myślałeś. Ale muszę cię ostrzec, wszyscy mówią o tym, jak ładna jest rekurencja i jak wiele prostoty wnosi do kodu, biorąc pod uwagę, że mam kilka rzeczy do powiedzenia:

  1. Po pierwsze, myślenie o „rekurencyjnym sposobie” algorytmu nie jest łatwe. Zbudowanie funkcji silni (n!) Lub czegoś w rodzaju wież Hanoi to tylko wierzchołek góry lodowej, a osiągnięcie dna wymaga dłuższego czasu.
  2. Nie myśl, że rekurencja wprowadza prostotę tylko do twojego kodu, czasami iteracyjny sposób jest brzydki i bałagan, ale jest opłacalny (spójrz na rekurencyjne rozwiązanie problemu Fibonacciego)

Mając to na uwadze, naucz się rekurencji! to zabawne, złożone i rozbije ci mózg !, ale pokochasz to.

Powodzenia!

David Conde
źródło