Rekurencja lub pętle while

Czytałem o niektórych praktykach podczas wywiadów programistycznych, w szczególności o pytaniach technicznych i testach zadawanych podczas wywiadów i kilkakrotnie potknąłem się o powieści gatunku: „Ok rozwiązałeś problem z pętlą while, teraz możesz to zrobić z rekurencja ”lub„ każdy może rozwiązać ten problem za pomocą 100 linii podczas pętli, ale czy może to zrobić za pomocą funkcji rekurencyjnej 5 linii? ” itp.

Moje pytanie brzmi: czy rekurencja jest ogólnie lepsza niż jeśli / podczas / dla konstruktów?

Szczerze mówiąc zawsze myślałem, że rekurencja nie jest preferowana, ponieważ jest ograniczona do pamięci stosu, która jest znacznie mniejsza niż sterta, a także wykonywanie dużej liczby wywołań funkcji / metod jest nieoptymalne z punktu widzenia wydajności, ale mogę mylić się...

Rekurencja nie jest z natury lepsza ani gorsza od pętli - każda ma zalety i wady, a te nawet zależą od języka programowania (i implementacji).

Technicznie pętle iteracyjne lepiej pasują do typowych systemów komputerowych lepiej na poziomie sprzętowym: na poziomie kodu maszynowego, pętla jest tylko testem i skokiem warunkowym, podczas gdy rekurencja (implementowana naiwnie) polega na wypychaniu ramki stosu, przeskakiwaniu, powracaniu i cofaniu się ze stosu. OTOH, można zapisać wiele przypadków rekurencji (szczególnie te, które są w trywialny sposób równoważne z iteracyjnymi pętlami), dzięki czemu można uniknąć push / pop stosu; jest to możliwe, gdy rekurencyjne wywołanie funkcji jest ostatnią rzeczą, która dzieje się w treści funkcji przed powrotem, i jest powszechnie znane jako optymalizacja wywołania ogona (lub optymalizacja rekurencji ogona ). Odpowiednio zoptymalizowana funkcja rekurencyjna zoptymalizowana pod kątem wywołania ogona jest w większości odpowiednikiem pętli iteracyjnej na poziomie kodu maszynowego.

Inną kwestią jest to, że pętle iteracyjne wymagają aktualizacji stanu destrukcyjnego, co czyni je niezgodnymi z semantyką języka czystego (bez skutków ubocznych). To jest powód, dla którego czyste języki, takie jak Haskell, w ogóle nie mają konstrukcji pętli, a wielu innym językom programowania funkcjonalnego brakuje ich całkowicie lub w jak największym stopniu ich unikają.

Powodem, dla którego pytania te pojawiają się tak często w wywiadach, jest to, że aby odpowiedzieć na nie, potrzebujesz dokładnego zrozumienia wielu istotnych pojęć programistycznych - zmiennych, wywołań funkcji, zakresu oraz oczywiście pętli i rekurencji - i masz aby przynieść mentalną elastyczność do stołu, która pozwala podejść do problemu z dwóch radykalnie różnych punktów widzenia i przechodzić między różnymi przejawami tej samej koncepcji.

Doświadczenie i badania sugerują, że istnieje granica między ludźmi, którzy potrafią zrozumieć zmienne, wskaźniki i rekurencję, a tymi, którzy tego nie rozumieją. Prawie wszystko inne w programowaniu, w tym frameworki, interfejsy API, języki programowania i ich najważniejsze przypadki, można zdobyć poprzez studiowanie i doświadczenie, ale jeśli nie jesteś w stanie rozwinąć intuicji dla tych trzech podstawowych pojęć, nie jesteś programistą. Tłumaczenie prostej pętli iteracyjnej na wersję rekurencyjną jest najszybszym możliwym sposobem odfiltrowania osób niebędących programistami - nawet raczej niedoświadczony programista może to zrobić zwykle w ciągu 15 minut i jest to bardzo problematyczny język, więc kandydat może wybrać wybrany przez nich język zamiast potykania się o osobliwości.

Jeśli w trakcie rozmowy otrzymasz takie pytanie, to dobry znak: oznacza to, że potencjalny pracodawca szuka ludzi, którzy mogą programować, a nie osób, które zapamiętały instrukcję obsługi narzędzia programistycznego.

To zależy.

• Niektóre problemy są bardzo podatne na rozwiązania rekurencyjne, np. Quicksort
• Niektóre języki tak naprawdę nie obsługują rekurencji, np. Wczesne FORTRANY
• Niektóre języki zakładają rekurencję jako podstawowy sposób zapętlenia, np. Haskell

Warto również zauważyć, że wsparcie dla rekurencji ogona sprawia, że ​​rekurencyjne ogony i pętle iteracyjne są równoważne, co oznacza, że ​​rekurencja nie zawsze musi marnować stos.

Ponadto algorytm rekurencyjny można zawsze zaimplementować iteracyjnie , używając jawnego stosu .

Na koniec chciałbym zauważyć, że rozwiązanie pięcioliniowe jest prawdopodobnie zawsze lepsze niż 100-liniowe (zakładając, że faktycznie są one równoważne).

Nie ma powszechnie uzgodnionej definicji „lepszego”, jeśli chodzi o programowanie, ale wezmę to za „łatwiejsze w utrzymaniu / czytaniu”.

Rekurencja ma większą moc ekspresji niż iteracyjne konstrukcje zapętlenia: Mówię to, ponieważ pętla while jest równoważna funkcji rekurencyjnej ogona, a funkcje rekurencyjne nie muszą być rekurencyjne. Potężne konstrukcje są zwykle złą rzeczą, ponieważ pozwalają ci robić rzeczy, które są trudne do odczytania. Jednak rekurencja daje możliwość pisania pętli bez korzystania ze zmienności, a moim zdaniem zmienność jest znacznie potężniejsza niż rekurencja.

Tak więc, od niskiej mocy ekspresyjnej po wysoką moc ekspresyjną, zapętlone konstrukcje układają się w następujący sposób:

• Funkcje rekurencyjne Tail, które wykorzystują niezmienne dane,
• Funkcje rekurencyjne wykorzystujące niezmienne dane,
• Podczas gdy pętle wykorzystują zmienne dane,
• Funkcje rekurencyjne Tail, które wykorzystują zmienne dane,
• Funkcje rekurencyjne wykorzystujące dane zmienne,

Idealnie byłoby użyć najmniej ekspresyjnych konstrukcji, jakie możesz. Oczywiście, jeśli Twój język nie obsługuje optymalizacji wywołania ogona, może to również wpłynąć na wybór konstrukcji zapętlonej.

Rekurencja jest często mniej oczywista. Mniej oczywiste jest trudniejsze do utrzymania.

Jeśli piszesz for(i=0;i<ITER_LIMIT;i++){somefunction(i);}w głównym nurcie, doskonale wyjaśniasz, że piszesz pętlę. Jeśli piszesz somefunction(ITER_LIMIT);, tak naprawdę nie wyjaśniasz, co się stanie. Wyświetlanie tylko treści: somefunction(int x)wywołania te somefunction(x-1)informują, że w rzeczywistości jest to pętla korzystająca z iteracji. Ponadto, nie możesz łatwo ustawić warunku ucieczki break;gdzieś w połowie iteracji, musisz albo dodać warunek, który zostanie przekazany do końca, albo zgłosić wyjątek. (a wyjątki znów zwiększają złożoność ...)

Zasadniczo, jeśli jest to oczywisty wybór między iteracją a rekurencją, zrób intuicyjnie. Jeśli iteracja wykona zadanie łatwo, zaoszczędzenie 2 linii jest rzadko warte bólu głowy, który może powodować na dłuższą metę.

Oczywiście, jeśli oszczędza Ci 98 linii, to zupełnie inna sprawa.

Są sytuacje, w których rekurencja po prostu idealnie pasuje i nie są tak naprawdę rzadkie. Przejście struktur drzewiastych, wielokrotnie połączonych sieci, struktur, które mogą zawierać własny typ, wielowymiarowe poszarpane tablice, w zasadzie wszystko, co nie jest ani prostym wektorem, ani tablicą o stałych wymiarach. Jeśli przemierzasz znaną, prostą ścieżkę, iteruj. Jeśli zanurkujesz w nieznane, wróć.

Zasadniczo, jeśli somefunction(x-1)ma być wywoływany z siebie więcej niż jeden raz na poziom, zapomnij o iteracjach.

... Pisanie iteracyjnie funkcji dla zadań najlepiej wykonywanych przez rekurencję jest możliwe, ale nie przyjemne. Gdziekolwiek chcesz użyć int, potrzebujesz czegoś takiego stack<int>. Zrobiłem to raz, bardziej jako ćwiczenie niż dla celów praktycznych. Zapewniam cię, że kiedy staniesz przed takim zadaniem, nie będziesz mieć wątpliwości, jak te, które wyraziłeś.

Jak zwykle na ogół nie da się odpowiedzieć, ponieważ istnieją dodatkowe czynniki, które w praktyce są zasadniczo nierówne między przypadkami i nierówne względem siebie w przypadku użycia. Oto niektóre z presji.

• Krótki, elegancki kod jest ogólnie lepszy od długiego, skomplikowanego kodu.
• Jednak ostatni punkt jest nieco nieważny, jeśli baza programistów nie jest zaznajomiona z rekurencją i nie chce / nie może się uczyć. Może nawet stać się nieznacznie negatywny niż pozytywny.
• Rekurencja może mieć negatywny wpływ na wydajność, jeśli będziesz potrzebować głęboko zagnieżdżonych połączeń w praktyce i nie będziesz mógł użyć rekurencji ogona (lub twoje środowisko nie będzie w stanie zoptymalizować rekurencji ogona).
• Rekurencja jest również zła w wielu przypadkach, jeśli nie można prawidłowo buforować wyników pośrednich. Na przykład częsty przykład użycia rekurencji drzewa do obliczania liczb Fibonacciego działa strasznie źle, jeśli nie buforujesz. Jeśli robisz pamięć podręczną, jest to proste, szybkie, eleganckie i całkowicie wspaniałe.
• Rekurencja nie ma zastosowania w niektórych przypadkach, tak samo dobra jak iteracja w innych i absolutnie konieczna w jeszcze innych. Przeszukiwanie długich łańcuchów reguł biznesowych zwykle nie pomaga wcale. Iterowanie strumieniami danych można z powodzeniem wykonywać za pomocą rekurencji. Iteracja nad wielowymiarowymi dynamicznymi strukturami danych (np. Labirynty, drzewa obiektów ...) jest prawie niemożliwa bez rekurencji, wyraźnej lub dorozumianej. Zauważ, że w takich przypadkach jawna rekurencja jest znacznie lepsza niż domniemana - nic nie jest bardziej bolesne niż czytanie kodu, w którym ktoś zaimplementował swój własny, niekompletny, błędny stos w języku, aby uniknąć przerażającego słowa R.

Rekurencja polega na powtarzaniu wywołania funkcji, pętla polega na powtarzaniu przeskoku do miejsca w pamięci.

Należy również wspomnieć o przepełnieniu stosu - http://en.wikipedia.org/wiki/Stack_overflow

To zależy od wygody lub wymagania:

Jeśli weźmiesz język programowania Python , obsługuje on rekurencję, ale domyślnie istnieje limit głębokości rekurencji (1000). Jeśli przekroczy limit, otrzymamy błąd lub wyjątek. Limit ten można zmienić, ale jeśli to zrobimy, możemy doświadczyć nienormalnych sytuacji w języku.

W tej chwili (liczba wywołań większa niż głębokość rekurencji) musimy preferować konstrukcje pętli. To znaczy, jeśli rozmiar stosu nie jest wystarczający, musimy preferować konstrukcje pętli.

Użyj wzorca projektowania strategii.

• Rekursja jest czysta
• Pętle są (prawdopodobnie) wydajne

W zależności od obciążenia (i / lub innych warunków) wybierz jeden.