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?
recursion
advantages
OscarRyz
źródło
źródło
Odpowiedzi:
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
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.
źródło
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?
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.
źródło
Prostota. Bez optymalizacji wywołania ogonowego wymaga to oczywiście więcej zasobów (stosu), ale jak zaimplementowałbyś, powiedzmy,
deltree
w Javie bez rekurencji? Rzecz w tym, żedelete()
można usuwać katalogi tylko wtedy, gdy są puste; oto z rekurencją:źródło
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:
Mając to na uwadze, naucz się rekurencji! to zabawne, złożone i rozbije ci mózg !, ale pokochasz to.
Powodzenia!
źródło