Czy pętla while jest z natury rekurencją?

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?

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.

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.

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

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.

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.

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

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.

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.

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

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.

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