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

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?

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.

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.

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.

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

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!