Rekurencja lub pętle while

123

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ę...

Shivan Dragon
źródło
73
Jeśli chodzi o rekurencję, wygląda to dość interesująco.
dan_waterworth
4
@dan_waterworth również, to pomogłoby: google.fr/... ale zawsze wydaje mi się, że to przeliteruję: P
Shivan Dragon
@ShivanDragon Myślałem tak ^ _ ^ Bardzo dobrze, że opublikowałem to wczoraj :-)
Neal
2
W środowiskach osadzonych, nad którymi pracowałem w rekursji, jest co najwyżej marne spojrzenie, aw najgorszym przypadku publicznie chłosta się. Ograniczone miejsce na stosie powoduje, że jest to nielegalne.
Fred Thomsen

Odpowiedzi:

192

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.

tdammers
źródło
3
Najbardziej podoba mi się twoja odpowiedź, ponieważ dotyczy ona najważniejszych aspektów odpowiedzi na to pytanie, wyjaśnia główne części techniczne, a także daje dobre pomniejszone spojrzenie na to, jak ten problem pasuje do sfery programowania.
Shivan Dragon,
1
Zauważyłem również wzorzec w programowaniu synchronizacji, w którym unika się pętli na rzecz wywołań rekurencyjnych w iteratorze, który zawiera metodę .next (). Zakładam, że sprawia, że ​​długo działający kod nie staje się zbyt chciwy CPU.
Evan Plaice,
1
Wersja iteracyjna obejmuje także wypychanie i usuwanie wartości. Musisz tylko ręcznie napisać kod, aby to zrobić. Wersja rekurencyjna wypycha stan na stos w iteracyjnym algorytmie, który zwykle trzeba ręcznie symulować, wpychając stan do jakiejś struktury. Tylko najbardziej trywialne algorytmy nie potrzebują tego stanu. W takich przypadkach kompilator zwykle może wykryć rekurencję ogona i stworzyć iteracyjne rozwiązanie.
Martin York
1
@tdammers Czy możesz mi powiedzieć, gdzie mogę przeczytać badanie, o którym wspominałeś „Doświadczenie i badania sugerują, że istnieje granica między ludźmi ...” Wydaje mi się to bardzo interesujące.
Yoo Matsuo,
2
Jedną rzecz, o której zapomniałeś wspomnieć, kod iteracyjny zwykle działa lepiej, gdy masz do czynienia z jednym wątkiem wykonania, ale algorytmy rekurencyjne zwykle nadają się do wykonywania w wielu wątkach.
GordonM
37

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).

jk.
źródło
5
Dobra odpowiedź (+1). „Rozwiązanie 5-liniowe jest prawdopodobnie zawsze lepsze niż 100-liniowe”: Myślę, że zwięzłość nie jest jedyną zaletą rekurencji. Korzystanie z wywołania rekurencyjnego wymusza wyraźne określenie zależności funkcjonalnych między wartościami w różnych iteracjach.
Giorgio
4
Krótsze rozwiązania wydają się być lepsze, ale istnieje coś takiego, jak zbyt zwięzłe.
dan_waterworth
5
@dan_waterworth w porównaniu do „linii 100” raczej trudno jest być zbyt zwięzłym
komara
4
@Giorgio, Możesz zmniejszyć programy, usuwając niepotrzebny kod lub wprowadzając jawne rzeczy. Dopóki trzymasz się tego pierwszego, poprawiasz jakość.
dan_waterworth
1
@jk, myślę, że to kolejna forma domniemanej jawnej informacji. Informacja o tym, do czego używana jest zmienna, jest usuwana z jej nazwy, gdzie jest jawna, i jest przekazywana do jej użycia, które jest niejawne.
dan_waterworth
17

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.

dan_waterworth
źródło
1
„pętla while jest równoważna funkcji rekurencyjnej ogona, a funkcje rekurencyjne nie muszą być rekurencyjne”: +1. Możesz symulować rekurencję za pomocą pętli while + stosu.
Giorgio
1
Nie jestem pewien, czy zgadzam się w 100%, ale z pewnością jest to interesująca perspektywa, więc +1 za to.
Konrad Rudolph
+1 za świetną odpowiedź, a także za wspomnienie, że niektóre języki (lub kompilatory) nie wykonują optymalizacji połączeń ogonowych.
Shivan Dragon,
@Giorgio, „Możesz symulować rekurencję za pomocą pętli while + stosu”, dlatego powiedziałem moc ekspresyjną. Pod względem obliczeniowym są równie potężne.
dan_waterworth
@dan_waterworth: Dokładnie i jak powiedziałeś w swojej odpowiedzi, sama rekurencja jest bardziej ekspresyjna niż pętla while, ponieważ musisz dodać stos do pętli while, aby zasymulować rekurencję.
Giorgio
7

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ś.

SF.
źródło
10
To, co jest oczywiste, a co mniej oczywiste, zależy częściowo od tego, do czego jesteś przyzwyczajony. Iteracja była częściej stosowana w językach programowania, ponieważ jest ona bliższa sposobowi pracy procesora (tzn. Zużywa mniej pamięci i działa szybciej). Ale jeśli jesteś przyzwyczajony do myślenia indukcyjnego, rekurencja może być równie intuicyjna.
Giorgio
5
„Jeśli zobaczą słowo kluczowe pętli, wiedzą, że jest to pętla. Ale nie ma słowa kluczowego rekurencyjnego, mogą je rozpoznać, widząc f (x-1) wewnątrz f (x).”: Kiedy wywołujesz funkcję rekurencyjną, robisz nie chcę wiedzieć, że jest rekurencyjny. Podobnie, gdy wywołujesz funkcję zawierającą pętlę, nie chcesz wiedzieć, że zawiera ona pętlę.
Giorgio
3
@SF: Tak, ale możesz to zobaczyć tylko wtedy, gdy spojrzysz na treść funkcji. W przypadku pętli widzisz pętlę, w przypadku rekurencji widzisz, że funkcja sama się wywołuje.
Giorgio
5
@SF: Wydaje mi się to trochę okrągłym rozumowaniem: „Jeśli w mojej intuicji jest to pętla, to jest to pętla”. mapmożna zdefiniować jako funkcję rekurencyjną (patrz np. haskell.org/tutorial/functions.html ), nawet jeśli intuicyjnie jest jasne, że przegląda listę i stosuje funkcję do każdego członka listy.
Giorgio
5
@SF mapnie jest słowem kluczowym, jest zwykłą funkcją, ale to trochę nieistotne. Gdy programiści funkcjonalni używają rekurencji, zwykle nie dzieje się tak dlatego, że chcą wykonać sekwencję działań, ponieważ rozwiązany problem można wyrazić jako funkcję i listę argumentów. Problem można następnie zredukować do innej funkcji i innej listy argumentów. W końcu masz problem, który można rozwiązać w trywialny sposób.
dan_waterworth
6

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.
Kilian Foth
źródło
Co rozumiesz przez buforowanie w odniesieniu do rekurencji?
Giorgio
@Giorgio prawdopodobnie memoization
jk.
Feh. Jeśli twoje środowisko nie optymalizuje wywołań ogonowych, powinieneś znaleźć lepsze środowisko, a jeśli programiści nie są zaznajomieni z rekurencją, powinieneś znaleźć lepszych programistów. Miejcie pewne standardy, ludzie!
CA McCann,
1

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

okobaka
źródło
1
Rekurencja oznacza funkcję, której definicja wymaga samodzielnego wywołania.
hardmath
1
Podczas gdy twoja prosta definicja nie jest dokładnie 100% dokładna, jesteś jedyną, która wspomniała o przepełnieniu stosu.
Qix
1

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.

usernaveen
źródło
3
Oto blog Guido van Rossuma wyjaśniający, dlaczego nie chce optymalizacji rekurencji ogona w Pythonie (popierając pogląd, że różne języki mają różne podejścia taktyczne).
hardmath
-1

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.

Pravin Sonawane
źródło
5
Czekaj, co? W jaki sposób pasuje tu wzór strategii? Drugie zdanie brzmi jak puste zdanie.
Konrad Rudolph
@KonradRudolph Wybrałbym rekursję. W przypadku bardzo dużych zestawów danych przełączałbym się na pętle. O to mi chodziło. Przepraszam, jeśli nie było jasne.
Pravin Sonawane
3
Ach Cóż, nadal nie jestem pewien, czy można to nazwać „wzorcem projektowania strategii”, który ma bardzo ustalone znaczenie i używasz go metaforycznie. Ale teraz przynajmniej widzę, dokąd zmierzasz.
Konrad Rudolph
@KonradRudolph nauczył się ważnej lekcji. Dokładnie wyjaśnij, co chcesz powiedzieć .. Dzięki .. to pomogło .. :)
Pravin Sonawane
2
@Pravin Sonawane: Jeśli możesz użyć optymalizacji rekurencji ogona, możesz użyć rekurencji również na dużych zestawach danych.
Giorgio