Czy pętla while jest z natury rekurencją?

37

Zastanawiałem się, czy pętla while jest z natury rekurencją?

Myślę, że dzieje się tak, ponieważ pętla while może być postrzegana jako funkcja, która wywołuje się na końcu. Jeśli nie jest to rekurencja, to jaka jest różnica?

do widzenia
źródło
13
Możesz przekonwertować rekurencję na iterację i odwrotnie, tak. To nie znaczy, że są takie same, po prostu mają te same możliwości. Są chwile, kiedy rekurencja jest bardziej naturalna i są chwile, w których iteracja jest bardziej naturalna.
Polygnome
18
@MooingDuck Możesz przez indukcję udowodnić, że każdą rekurencję można zapisać jako iterację i odwrotnie. Tak, będzie wyglądać zupełnie inaczej, ale i tak możesz to zrobić.
Polygnome
6
Co samo w sobie oznacza to samo ? W programowaniu użycie rekurencji oznacza określoną rzecz, która różni się od iteracji (pętli). W CS, kiedy zbliżasz się do teoretycznej strony matematyki, te rzeczy zaczynają znaczyć nieco inne rzeczy.
hyde
3
@MooingDuck Konwersja z rekurencyjnego na iteracyjny jest w rzeczywistości dość trywialna. Po prostu przechowujesz stos parametrów wywołania funkcji i stos wyników dla wywołań funkcji. Zastępujesz wywołania rekurencyjne, dodając parametry do stosu wywołań. pewnie jest cała obsługa stosu, która trochę psuje strukturę algorytmu, ale kiedy zrozumiesz, dość łatwo jest zauważyć, że kod robi to samo. Zasadniczo piszesz stos wywołań, który jest niejawny w definicjach rekurencyjnych.
Bakuriu

Odpowiedzi:

116

Pętle nie są rekurencyjne. W rzeczywistości są one najlepszym przykładem mechanizmu przeciwnego : iteracji .

Punktem rekurencji jest to, że jeden element przetwarzania wywołuje inną instancję samego siebie. Maszyna kontroli pętli po prostu przeskakuje z powrotem do punktu, w którym się rozpoczęła.

Przeskakiwanie w kodzie i wywoływanie innego bloku kodu to różne operacje. Na przykład, kiedy przeskakujesz na początek pętli, zmienna kontrolna pętli nadal ma tę samą wartość, co przed skokiem. Ale jeśli wywołasz inną instancję procedury, w której się znajdujesz, nowa instancja ma nowe, niepowiązane kopie wszystkich swoich zmiennych. W efekcie jedna zmienna może mieć jedną wartość na pierwszym poziomie przetwarzania, a drugą wartość na niższym poziomie.

Ta zdolność jest kluczowa dla działania wielu algorytmów rekurencyjnych i dlatego nie można emulować rekurencji poprzez iterację bez zarządzania stosem zwanych ramek, który śledzi wszystkie te wartości.

Kilian Foth
źródło
10
@Giorgio To może być prawda, ale jest to komentarz do roszczenia, którego nie udzieliła odpowiedź. „Arbitralnie” nie występuje w tej odpowiedzi i znacząco zmienia znaczenie.
hvd
12
@hvd Zasadniczo rekursja ogona jest rekurencją jak każda inna. Inteligentne kompilatory mogą zoptymalizować rzeczywistą część „tworzenia nowej ramki stosu”, dzięki czemu wygenerowany kod jest bardzo podobny do pętli, ale koncepcje, o których mówimy, dotyczą poziomu kodu źródłowego. Uważam formę, jaką algorytm ma za kod źródłowy, za ważną rzecz, więc nadal nazwałbym to rekurencją
Kilian Foth
15
@Giorgio „to właśnie robi rekurencja: wywołuje się z nowymi argumentami” - z wyjątkiem wywołania. I argumenty.
hobbs
12
@Giorgio Używasz różnych definicji słów niż większość tutaj. Słowa, wiesz, są podstawą komunikacji. To są programiści, a nie CS Stack Exchange. Gdybyśmy użyli słów takich jak „argument”, „wywołanie”, „funkcja” itp., Jak sugerujesz, niemożliwe byłoby omówienie rzeczywistego kodu.
hyde
6
@Giorgio Patrzę na abstrakcyjną koncepcję. Istnieje koncepcja, w której powracasz, i koncepcja, w której zapętlasz się. To różne koncepcje. Hobbs ma 100% poprawności, że nie ma argumentów i nie ma wywołania. Są zasadniczo i abstrakcyjnie różne. I to dobrze, ponieważ rozwiązują różne problemy. Ty natomiast zastanawiasz się, jak zaimplementować pętle, gdy jedynym narzędziem jest rekurencja. Ironiczne, mówisz Hobbsowi, żeby przestał myśleć o wdrożeniu i zaczął patrzeć na koncepcje, kiedy twoja metodologia naprawdę wymaga ponownej oceny.
corsiKa
37

Mówienie, że X jest z natury Y, ma sens tylko wtedy, gdy masz jakiś (formalny) system, w którym wyrażasz X. Jeśli zdefiniujesz semantykę whilew kategoriach rachunku lambda, możesz wspomnieć o rekurencji *; jeśli zdefiniujesz to jako maszynę rejestrującą, prawdopodobnie nie będziesz.

W obu przypadkach ludzie prawdopodobnie cię nie zrozumieją, jeśli wywołasz funkcję rekurencyjną tylko dlatego, że zawiera ona pętlę while.

* Chociaż być może tylko pośrednio, na przykład jeśli zdefiniujesz to w kategoriach fold.

Anton Golov
źródło
4
Szczerze mówiąc, funkcja nie jest rekurencyjna w żadnej definicji. Zawiera tylko element rekurencyjny, pętlę.
Luaan,
@Luaan: Zdecydowanie tak, ale ponieważ w językach z whilekonstrukcją rekurencyjność jest ogólnie własnością funkcji, po prostu nie mogę wymyślić niczego innego, co można by opisać jako „rekurencyjne” w tym kontekście.
Anton Golov
36

To zależy od twojego punktu widzenia.

Jeśli spojrzysz na teorię obliczalności , to iteracja i rekurencja są równie ekspresyjne . Oznacza to, że możesz napisać funkcję, która coś oblicza, i nie ma znaczenia, czy zrobisz to rekurencyjnie, czy iteracyjnie, będziesz mógł wybrać oba podejścia. Nie ma nic, co można obliczyć rekurencyjnie, czego nie można obliczyć iteracyjnie i vice versa (chociaż wewnętrzne działanie programu może być inne).

Wiele języków programowania nie traktuje rekurencji i iteracji tak samo i nie bez powodu. Zwykle rekurencja oznacza, że ​​język / kompilator obsługuje stos wywołań, a iteracja oznacza, że ​​będziesz musiał samodzielnie obsługiwać stosy.

Istnieją jednak języki - zwłaszcza języki funkcjonalne - w których pętle (for, while) są w rzeczywistości jedynie cukrem syntaktycznym do rekurencji i są realizowane za kulisami. Jest to często pożądane w językach funkcjonalnych, ponieważ zwykle nie mają oni pojęcia zapętlania, a dodanie ich uczyniłoby ich rachunek bardziej skomplikowanym, z niewielkiego praktycznego powodu.

Więc nie, nie są one z natury takie same . Są równie ekspresyjne , co oznacza, że ​​nie można obliczyć czegoś iteracyjnie, nie można obliczyć rekurencyjnie i odwrotnie, ale o to chodzi w ogólnym przypadku (zgodnie z tezą Churcha-Turinga).

Zauważ, że mówimy tutaj o programach rekurencyjnych . Istnieją inne formy rekurencji, np. W strukturach danych (np. Drzewach).


Jeśli spojrzysz na to z punktu widzenia implementacji , rekurencja i iteracja nie są prawie takie same. Rekurencja tworzy nową ramkę stosu dla każdego połączenia. Każdy etap rekurencji jest samowystarczalny, uzyskując argumenty do obliczeń od samego odbiorcy.

Z drugiej strony pętle nie tworzą ramek połączeń. Dla nich kontekst nie jest zachowywany na każdym kroku. W przypadku pętli program po prostu przeskakuje z powrotem na początek pętli, dopóki warunek pętli się nie powiedzie.

Jest to bardzo ważne, aby wiedzieć, ponieważ może powodować dość radykalne różnice w prawdziwym świecie. W przypadku rekurencji cały kontekst musi być zapisany przy każdym połączeniu. W przypadku iteracji masz precyzyjną kontrolę nad tym, jakie zmienne są w pamięci i gdzie są zapisywane.

Jeśli spojrzysz na to w ten sposób, szybko zauważysz, że w większości języków iteracja i rekurencja są zasadniczo różne i mają różne właściwości. W zależności od sytuacji niektóre właściwości są bardziej pożądane niż inne.

Rekurencja może uczynić programy prostszymi i łatwiejszymi do przetestowania i sprawdzenia . Konwersja rekurencji na iterację zwykle sprawia, że ​​kod jest bardziej złożony, zwiększając prawdopodobieństwo niepowodzenia. Z drugiej strony konwersja do iteracji i zmniejszenie liczby ramek stosu wywołań może zaoszczędzić bardzo potrzebną pamięć.

Polygnome
źródło
Język z lokalnymi zmiennymi i rekurencją, ale żadne tablice nie mogą wykonywać zadań, których nie mógłby wykonać iteracyjny język ze zmiennymi lokalnymi i bez tablic. Na przykład zgłoś, czy dane wejściowe zawierają ciąg alfanumeryczny o nieznanej długości, po którym następuje spacja, a następnie znaki oryginalnego ciągu w odwrotnej kolejności.
supercat
3
Tak długo, jak język jest kompletny, może. Tablicę można łatwo zastąpić na przykład (podwójnie) połączoną listą. Mówiąc o iteracji lub rekurencji i tam, gdzie są one równe, ma sens tylko, jeśli porównasz dwa kompletne języki Turinga.
Polygnome,
Miałem na myśli tylko proste zmienne statyczne lub automatyczne, tj. Brak kompletności Turinga. Język czysto iteracyjny byłby ograniczony do zadań, które można wykonać za pomocą prostego deterministycznego automatu skończonego, podczas gdy język rekurencyjny dodałby zdolność do wykonywania zadań, które wymagałyby przynajmniej deterministycznego automatu skończonego w dół.
supercat
1
Jeśli język nie jest kompletny, na początek nie ma sensu. DFA nie mogą wykonywać dowolnych iteracji ani rekurencji btw.
Polygnome,
2
Żadna implementacja nie jest tak naprawdę kompletna, a języki, które nie są kompletne, mogą być przydatne do wielu celów. DFA, w którym każda możliwa kombinacja wartości jest stanem dyskretnym, może obsłużyć dowolny program, który może być uruchamiany ze skończoną liczbą zmiennych o skończonym zakresie.
supercat
12

Różnica polega na domyślnym stosie i semantyce.

Pętla while, która „nazywa się na końcu”, nie ma stosu, który mógłby się czołgać po zakończeniu. Ostatnia iteracja określa, jaki stan będzie po zakończeniu.

Rekursji nie można jednak wykonać bez tego niejawnego stosu, który pamięta stan wcześniej wykonanej pracy.

Prawdą jest, że możesz rozwiązać każdy problem rekurencji z iteracją, jeśli wyraźnie umożliwisz mu dostęp do stosu. Ale robienie tego w ten sposób nie jest takie samo.

Różnica semantyczna ma związek z tym, że spojrzenie na kod rekurencyjny przekazuje ideę w zupełnie inny sposób niż kod iteracyjny. Kod iteracyjny robi wszystko krok po kroku. Akceptuje każdy stan, który pojawił się wcześniej i działa tylko w celu utworzenia następnego stanu.

Kod rekurencyjny dzieli problem na fraktale. Ta mała część wygląda jak ta duża część, dzięki czemu możemy zrobić ten fragment i tak samo. To inny sposób myślenia o problemach. Jest bardzo potężny i wymaga przyzwyczajenia się. Wiele można powiedzieć w kilku wierszach. Po prostu nie możesz wyciągnąć tego z pętli while, nawet jeśli ma on dostęp do stosu.

candied_orange
źródło
5
Myślę, że „ukryty stos” wprowadza w błąd. Rekurencja jest częścią semantyki języka, a nie szczegółem implementacji. (Oczywiście, większość języków obsługujących rekurencję używa stosu wywołań; ale po pierwsze, kilka takich języków nie, a po drugie, nawet w językach, które to robią, nie każde wywołanie rekurencyjne koniecznie dołącza się do stosu wywołań, ponieważ wiele języków obsługuje takie optymalizacje jako eliminacja wezwania ogona .) Zrozumienie zwykłej / prostej implementacji może być przydatne w opanowaniu abstrakcji, ale nie powinieneś oszukiwać się w myśleniu, że to cała historia.
ruakh
2
@ruakh Argumentowałbym, że funkcja, która wykonuje się w stałej przestrzeni za pomocą eliminacji wywołania ogona, naprawdę jest pętlą. Tutaj stos nie jest szczegółem implementacji, lecz abstrakcją, która pozwala kumulować różne stany dla różnych poziomów rekurencji.
Cimbali,
@ruakh: dowolny stan w ramach jednego wywołania rekurencyjnego zostanie zapisany na stosie niejawnym, chyba że kompilator może przekonwertować rekurencję w pętlę iteracyjną. Eliminacja wywołania ogonowego jest szczegółem implementacji, o którym musisz wiedzieć, jeśli chcesz zreorganizować swoją funkcję, aby była rekurencyjna. Ponadto, „kilka takich języków nie” - czy możesz podać przykład języków, które nie potrzebują stosu do wywołań rekurencyjnych?
Groo,
@ruakh: CPS sam w sobie tworzy ten sam ukryty stos, więc musi polegać na eliminacji wywołania ogona, aby mieć sens (co czyni go trywialnym ze względu na sposób jego budowy). Nawet artykuł w Wikipedii, do którego prowadziłeś link, mówi to samo: użycie CPS bez optymalizacji wywołania ogona (TCO) spowoduje, że nie tylko skonstruowana kontynuacja potencjalnie wzrośnie podczas rekurencji, ale także stos wywołań .
Groo,
7

To wszystkie zawiasy używaniem terminu samoistnie . Na poziomie języka programowania są one składniowo i semantycznie różne oraz mają zupełnie inną wydajność i wykorzystanie pamięci. Ale jeśli zagłębisz się wystarczająco głęboko w teorię, można je zdefiniować w kategoriach siebie, a zatem jest „taki sam” w pewnym sensie teoretycznym.

Prawdziwe pytanie brzmi: kiedy ma sens rozróżnianie między iteracją (pętlami) a rekurencją, a kiedy warto myśleć o tym jako o tych samych rzeczach? Odpowiedź jest taka, że ​​podczas programowania (w przeciwieństwie do pisania dowodów matematycznych) ważne jest, aby odróżnić iterację od rekurencji.

Rekurencja tworzy nową ramkę stosu, tj. Nowy zestaw zmiennych lokalnych dla każdego wywołania. Ma to narzut i zajmuje miejsce na stosie, co oznacza, że ​​wystarczająco głęboka rekurencja może przepełnić stos, co powoduje awarię programu. Z drugiej strony iteracja modyfikuje tylko istniejące zmienne, więc jest na ogół szybsza i zajmuje tylko stałą ilość pamięci. Jest to więc bardzo ważne wyróżnienie dla programisty!

W językach z rekurencją wywołania ogona (zwykle językami funkcjonalnymi) kompilator może być w stanie zoptymalizować wywołania rekurencyjne w taki sposób, że zajmuje tylko stałą ilość pamięci. W tych językach istotnym rozróżnieniem nie jest iteracja vs rekurencja, ale wersja bez rekurencji rekon-ogon rekurencja-iteracja.

Konkluzja: Musisz być w stanie powiedzieć różnicę, w przeciwnym razie program się zawiesi.

JacquesB
źródło
3

whilePętle są formą rekurencji, patrz np. zaakceptowana odpowiedź na to pytanie . Odpowiadają operatorowi μ w teorii obliczalności (patrz np. Tutaj ).

Wszystkie odmiany forpętli, które iterują w zakresie liczb, zbioru skończonego, tablicy itd., Odpowiadają prymitywnej rekurencji, patrz np. Tutaj i tutaj . Zauważ, że forpętle C, C ++, Java i tak dalej są w rzeczywistości cukrem syntaktycznym dla whilepętli i dlatego nie odpowiada prymitywnej rekurencji. forPętla Pascala jest przykładem prymitywnej rekurencji.

Ważną różnicą jest to, że pierwotna rekurencja zawsze kończy się, podczas gdy uogólniona rekurencja ( whilepętle) może się nie kończyć.

EDYTOWAĆ

Kilka wyjaśnień dotyczących komentarzy i innych odpowiedzi. „Rekurencja występuje, gdy rzecz jest zdefiniowana w kategoriach siebie lub swojego rodzaju”. (patrz wikipedia ). Więc,

Czy pętla while jest z natury rekurencją?

Ponieważ można zdefiniować whilesamą pętlę

while p do c := if p then (c; while p do c))

Następnie tak , A whilepętli formą rekursji. Funkcje rekurencyjne to kolejna forma rekurencji (inny przykład definicji rekurencyjnej). Listy i drzewa to inne formy rekurencji.

Kolejnym pytaniem, które jest domyślnie przyjmowane przez wiele odpowiedzi i komentarzy, jest

Czy pętle while i funkcje rekurencyjne są równoważne?

Odpowiedź na to pytanie brzmi : nie . whilePętla odpowiada funkcji rekurencyjnej ogona, gdzie zmienne, do których pętla ma dostęp, odpowiadają argumentom niejawnej funkcji rekurencyjnej, ale, jak zauważyli inni, funkcje nierekurencyjne nie można modelować za pomocą whilepętli bez użycia dodatkowego stosu.

A zatem fakt, że „ whilepętla jest formą rekurencji” nie przeczy faktowi, że „niektórych funkcji rekurencyjnych nie można wyrazić za pomocą whilepętli”.

Giorgio
źródło
2
@morbidCode: pierwotna rekurencja i μ-rekurencja są formami rekurencji ze szczególnymi ograniczeniami (lub ich brakiem), badanymi np. w teorii obliczalności. Jak się okazuje, język z samą FORpętlą może obliczyć dokładnie wszystkie prymitywne funkcje rekurencyjne, a język z samą WHILEpętlą może obliczyć dokładnie wszystkie funkcje μ-rekurencyjne (i okazuje się, że funkcje μ-rekurencyjne są dokładnie tymi funkcjami, które Maszyna Turinga może obliczyć). Krótko mówiąc: prymitywna rekurencja i µ-rekurencja są terminami technicznymi z matematyki / teorii obliczalności.
Jörg W Mittag
2
Myślałem, że „rekurencja” implikuje funkcję wywołującą samą siebie, co powoduje wypychanie bieżącego stanu wykonania na stos i tak dalej; dlatego większość maszyn ma praktyczne ograniczenie liczby powtórzeń. Podczas gdy pętle nie mają takich limitów, ponieważ wewnętrznie używają czegoś takiego jak „JMP” i nie używają stosu. Tylko moje zrozumienie może być błędne.
Jay
13
Ta odpowiedź używa zupełnie innej definicji słowa „rekurencyjna” niż OP, a zatem jest bardzo myląca.
Mooing Duck
2
@DavidGrinberg: Cytując: „C, C ++, Java dla pętli nie są przykładem pierwotnej rekurencji. Pierwotna rekurencja oznacza, że ​​maksymalna liczba iteracji / głębokość rekurencji jest ustalona przed uruchomieniem pętli.” Giorgio mówi o prymitywach teorii obliczalności . Nie ma związku z językami programowania.
Mooing Duck
3
Muszę się zgodzić z Mooing Duck. Chociaż teoria obliczalności może być interesująca w teoretycznym CS, myślę, że wszyscy zgadzają się, że OP mówił o koncepcji języków programowania.
Voo
2

Wezwanie ogon (lub ogon wywołanie rekurencyjne) jest dokładnie wdrażane jako „goto z argumentami” (bez pchania każdą dodatkową ramkę rozmowę na stosie wywołań ), aw niektórych językach funkcjonalnych (zwłaszcza Ocaml) jest zwykle sposobem pętli.

Tak więc pętla while (w języku, w którym ją posiada) może być postrzegana jako kończąca się wywołaniem ogona do jej ciała (lub testu głowy).

Podobnie zwykłe (inne niż wywołanie ogonowe) wywołania rekurencyjne mogą być symulowane przez pętle (przy użyciu stosu).

Przeczytaj także o kontynuacjach i stylu przekazywania kontynuacji .

Zatem „rekurencja” i „iteracja” są głęboko równoważne.

Basile Starynkevitch
źródło
1

Prawdą jest, że zarówno rekurencyjna, jak i nieograniczona pętla while są równoważne pod względem ekspresyjności obliczeniowej. Oznacza to, że każdy program napisany rekurencyjnie może zostać przepisany do równoważnego programu za pomocą pętli zamiast i odwrotnie. Oba podejścia są kompletne , czyli oba mogą być użyte do obliczenia dowolnej funkcji obliczeniowej.

Podstawowa różnica w zakresie programowania polega na tym, że rekurencja pozwala na wykorzystanie danych przechowywanych na stosie wywołań. Aby to zilustrować, załóżmy, że chcesz wydrukować elementy pojedynczo połączonej listy za pomocą pętli lub rekurencji. Użyję C jako przykładowego kodu:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Proste, prawda? Zróbmy teraz jedną drobną modyfikację: wydrukuj listę w odwrotnej kolejności.

W przypadku wariantu rekurencyjnego jest to prawie trywialna modyfikacja oryginalnej funkcji:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Mamy jednak problem z funkcją pętli. Nasza lista jest pojedynczo połączona i dlatego można ją przeglądać tylko do przodu. Ale ponieważ drukujemy w odwrotnej kolejności, musimy zacząć drukować ostatni element. Kiedy dotarliśmy do ostatniego elementu, nie możemy już powrócić do elementu od ostatniego do ostatniego.

Musimy więc albo wykonać wiele powtórek, albo zbudować pomocniczą strukturę danych, która będzie śledzić odwiedzane elementy i na podstawie których będziemy mogli wydajnie drukować.

Dlaczego nie mamy tego problemu z rekurencją? Ponieważ w rekursji mamy już strukturę danych pomocniczych: Stos wywołań funkcji.

Ponieważ rekurencja pozwala nam powrócić do poprzedniego wywołania wywołania rekurencyjnego, a wszystkie zmienne lokalne i stan dla tego połączenia są nadal nienaruszone, zyskujemy pewną elastyczność, która byłaby uciążliwa dla modelu w przypadku iteracji.

ComicSansMS
źródło
1
Oczywiście, druga funkcja rekurencyjna nie jest rekurencyjna - znacznie trudniej jest zoptymalizować przestrzeń, ponieważ nie można użyć TCO do ponownego użycia stosu. Wdrożenie podwójnie połączonej listy sprawiłoby, że oba algorytmy byłyby trywialne w obu przypadkach, kosztem przestrzeni wskaźnika / odwołania na element.
Baldrickk
@Baldrickk Zabawną rzeczą w rekursji ogona jest to, że kończy się wersja, która jest znacznie bliższa temu, jak wyglądałaby wersja pętli, ponieważ ponownie usuwa ona możliwość przechowywania stanu na stosie wywołań. Podwójnie połączona lista rozwiązałaby go, ale przeprojektowanie struktury danych często nie wchodzi w grę, gdy napotyka się ten problem. Chociaż przykład tutaj jest nieco sztucznie ograniczony, ilustruje on wzór, który często pojawia się w językach funkcjonalnych w kontekście rekurencyjnych typów algebraicznych.
ComicSansMS
Chodzi mi o to, że jeśli napotkasz ten problem, bardziej sprowadza się to do braku funkcjonalnego projektu, niż tego, jakich konstrukcji językowych używasz do jego implementacji, a każdy wybór ma swoje zalety i wady :)
Baldrickk
0

Pętle są specjalną formą rekurencji w celu osiągnięcia określonego zadania (głównie iteracji). Można zaimplementować pętlę w stylu rekurencyjnym o tej samej wydajności [1] w kilku językach. a w SICP [2] można zobaczyć, że pętle są opisane jako „cukier syntastyczny”. W większości imperatywnych języków programowania bloki for i while używają tego samego zakresu co ich funkcja nadrzędna. Niemniej jednak w większości funkcjonalnych języków programowania nie ma ani pętli for ani while, ponieważ nie ma ich potrzeby.

Powodem, dla którego imperatywne języki mają pętle for / while, jest to, że obsługują stany poprzez ich mutowanie. Ale tak naprawdę, jeśli spojrzysz z innej perspektywy, jeśli pomyślisz o bloku czasowym jako o samej funkcji, przyjmującym parametr, przetwarzającym go i zwracającym nowy stan - który równie dobrze może być wywołaniem tej samej funkcji z różnymi parametrami - możesz może myśleć o pętli jako o rekurencji.

Świat można również zdefiniować jako zmienny lub niezmienny. jeśli zdefiniujemy świat jako zestaw reguł i wywołamy funkcję ostateczną, która przyjmuje wszystkie reguły, a aktualny stan jako parametry, i zwrócimy nowy stan zgodnie z tymi parametrami, które mają tę samą funkcjonalność (wygeneruj następny stan w tym samym sposób), moglibyśmy równie dobrze powiedzieć, że jest to rekurencja i pętla.

w poniższym przykładzie życie jest funkcją, która przyjmuje dwa parametry „reguły” i „stan”, a nowy stan zostanie skonstruowany przy następnym zaznaczeniu.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: optymalizacja wywołania ogonowego jest powszechną optymalizacją w funkcjonalnych językach programowania w celu użycia istniejącego stosu funkcji w wywołaniach rekurencyjnych zamiast tworzenia nowego.

[2]: Struktura i interpretacja programów komputerowych, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

zeawee
źródło
4
@Giorgio Nie moja opinia negatywna, ale tylko przypuszczenie: myślę, że większość programistów uważa, że ​​rekurencja oznacza, że ​​istnieje wywołanie funkcji rekurencyjnej, ponieważ cóż, taka jest rekurencja, funkcja wywołująca samą siebie. W pętli nie ma rekurencyjnego wywołania funkcji. Zatem powiedzenie, że pętla bez wywołania funkcji rekurencyjnej jest specjalną formą rekurencji, byłoby rażąco błędne, gdyby przejść przez tę definicję.
hyde
1
Cóż, może patrząc na to z bardziej abstrakcyjnego punktu widzenia, to, co wydaje się być różnymi rzeczami, w rzeczywistości jest koncepcyjnie takie samo. Uważam, że dość zniechęcające i smutne jest myślenie, że ludzie odrzucają odpowiedzi tylko dlatego, że nie odpowiadają ich oczekiwaniom, zamiast wykorzystywać je jako szansę na naukę. Wszystkie odpowiedzi, które próbują powiedzieć: „Hej, spójrz, te rzeczy wyglądają inaczej na powierzchni, ale w rzeczywistości są takie same na bardziej abstrakcyjnym poziomie” zostały odrzucone.
Giorgio,
3
@Georgio: Celem tej witryny jest uzyskanie odpowiedzi na pytania. Odpowiedzi, które są pomocne i poprawne, zasługują na głosowanie, odpowiedzi, które są mylące i nieprzydatne, zasługują na głosowanie negatywne. Odpowiedź, która subtelnie wykorzystuje inną definicję wspólnego terminu, nie wyjaśniając, jaka jest inna definicja, jest myląca i nieprzydatna. Odpowiedzi, które mają sens tylko wtedy, gdy znasz odpowiedź, że tak powiem, nie są pomocne i służą jedynie do pokazania pisarzom lepszego zrozumienia terminologii.
JacquesB,
2
@JacquesB: „Odpowiedzi, które mają sens tylko wtedy, gdy znasz już odpowiedź, że tak powiem, nie są pomocne ...”: Można to również powiedzieć o odpowiedziach, które potwierdzają tylko to, co czytelnik już wie lub myśli o tym, że powinien wiedzieć. Jeśli odpowiedź wprowadza niejasną terminologię, możliwe jest napisanie komentarza z prośbą o dodatkowe szczegóły przed głosowaniem.
Giorgio,
4
Pętle nie są specjalną formą rekurencji. Spójrz na teorię obliczalności i np. Teoretyczny język PODCZAS i rachunek różniczkowy µ. Tak, niektóre języki używają pętli jako cukru syntaktycznego, aby faktycznie używać rekurencji za kulisami, ale mogą to zrobić, ponieważ rekurencja i iteracja są równie ekspresyjne , a nie dlatego, że są takie same.
Polygnome,
-1

Pętla while różni się od rekurencji.

Po wywołaniu funkcji następuje:

  1. Ramka stosu jest dodawana do stosu.

  2. Wskaźnik kodu przesuwa się na początek funkcji.

Po zakończeniu pętli while występują następujące zdarzenia:

  1. Warunek pyta, czy coś jest prawdą.

  2. Jeśli tak, kod przeskakuje do punktu.

Ogólnie rzecz biorąc, pętla while jest podobna do następującego pseudokodu:

 if (x)

 {

      Jump_to(y);

 }

Co najważniejsze, rekurencja i pętle mają różne reprezentacje kodu asemblacji i reprezentacje kodu maszynowego. Oznacza to, że nie są takie same. Mogą mieć takie same wyniki, ale inny kod maszynowy dowodzi, że nie są w 100% tym samym.

Wielka Kaczka
źródło
2
Mówisz o implementacji wywołania procedury i pętli while, a ponieważ są one implementowane inaczej, dochodzisz do wniosku, że są one różne. Jednak koncepcyjnie są one bardzo podobne.
Giorgio,
1
W zależności od kompilatora zoptymalizowane, wbudowane wywołanie rekurencyjne może równie dobrze wygenerować ten sam zestaw, co zwykła pętla.
hyde
@hyde ... który jest tylko przykładem dobrze znanego faktu, że jedno można wyrazić drugim; nie znaczy, że są identyczni. Trochę jak masa i energia. Oczywiście można argumentować, że wszystkie sposoby uzyskania identycznego wyniku są „takie same”. Gdyby świat był skończony, wszystkie programy byłyby na końcu constexpr.
Peter - Przywróć Monikę
@Giorgio Nah, to logiczny opis, a nie implementacja. Wiemy, że dwie rzeczy są równoważne ; ale równoważność nie jest tożsamością , ponieważ pytanie (i odpowiedzi) jest dokładnie tym , jak dochodzimy do wyniku, tj. muszą koniecznie zawierać opisy algorytmiczne (które można wyrazić w postaci stosu i zmiennej itp.).
Peter - Przywróć Monikę
1
@ PeterA.Schneider Tak, ale ta odpowiedź brzmi „Najważniejszy ze wszystkich… różnych kodów asemblerowych”, co nie jest całkiem poprawne.
hyde
-1

Sama iteracja jest niewystarczająca, aby generalnie odpowiadać rekurencji, ale iteracja ze stosem jest ogólnie równoważna. Każda funkcja rekurencyjna może zostać przeprogramowana jako pętla iteracyjna ze stosem i odwrotnie. Nie oznacza to jednak, że jest to praktyczne, aw każdej konkretnej sytuacji jedna lub druga forma może mieć wyraźne zalety w stosunku do drugiej wersji.

Nie jestem pewien, dlaczego jest to kontrowersyjne. Rekurencja i iteracja ze stosem to ten sam proces obliczeniowy. Można powiedzieć, że są tym samym „fenomenem”.

Jedyne, o czym mogę myśleć, to to, że patrząc na nie jako na „narzędzia programistyczne”, zgodziłbym się, że nie powinniście myśleć o nich jako o tej samej rzeczy. Są równoważne „matematycznie” lub „obliczeniowo” (ponownie iteracja ze stosem , a nie iteracja w ogóle), ale to nie znaczy, że powinieneś podejść do problemów z myślą, że którekolwiek z nich zrobi. Z punktu widzenia implementacji / rozwiązywania problemów niektóre problemy mogą działać lepiej w taki czy inny sposób, a Twoim zadaniem jako programisty jest prawidłowe wybranie, który z nich jest bardziej odpowiedni.

Aby wyjaśnić, odpowiedź na pytanie Czy pętla while jest wewnętrznie rekurencją? jest zdecydowanie nie , a przynajmniej „nie, chyba że masz również stos”.

Dave Cousineau
źródło